solutionsen
Algorithm Experiment Problem Set
Xiaodong W ang
(wangxd@https://www.wendangku.net/doc/2d12438284.html,)
Department of Computer Science
Fuzhou University P.R.China
Jun., 2007
Chapter 1 Introduction
Problem 1.1 Counting
Problem 1.2 Dictionary
Problem 1.3 Divisors
Problem 1.4 Coin Array
Problem 1.5 Maximum Gap
Chapter 2 Recursion and Divide and Conquer Problem 2.1 Pipeline
Problem 2.2 Majority
Problem 2.3 Post Office
Problem 2.4 Knight’s Hamilton Tour Problem 2.5 Half Multiset
Problem 2.6 Half Set
Problem 2.7 Soldiers
Problem 2.8 Permutation with Repetition Problem 2.9 Lexicographic Order
Problem 2.10 Set Partition
Problem 2.11 Set Partition 2
Problem 2.12 Bicolor Towers of Hanoi Problem 2.13 Standard 2′n Table
Problem 2.14 Integer Factorization
Problem 2.15 Sawmills
Chapter 3 Dynamic Programming
Problem 3.1 Independent Task Scheduling Problem 3.2 Coin Changing
Problem 3.3 Relation Ordering
Problem 3.4 Counting Powers
Problem 3.5 Edit Distance
Problem 3.6 Pebble Merging
Problem 3.7 Number Triangles
Problem 3.8 Multiplication Table
Problem 3.9 Renting Boats
Problem 3.10 Car Traveling
Problem 3.11 Circle Multiplication Problem 3.12 Cheapest Shopping
Problem 3.13 Maximum Cube
Problem 3.14 Regular Expressions
Problem 3.15 Bitonic Tours
Problem 3.16 Maximum k Multiplications Problem 3.17 Minimal m Sums
Problem 3.18 Red Nodes of Red-Black Trees Chapter 4 Greedy Algorithms
Problem 4.1 Lecture Halls
Problem 4.2 Optimal Merge
Problem 4.3 Program Storage
Problem 4.4 Optimal Program Storage
Problem 4.5 Program Storage
Problem 4.6 Optimal Services
Problem 4.7 Optimal Many Services
Problem 4.8 d Forest
Problem 4.9 Oiling Car
Problem 4.10 Interval Cover
Problem 4.11 Coin Changing
Problem 4.12 Delete Numbers
Problem 4.13 Maximum Sequence Differences Problem 4.14 Nesting Boxes
Problem 4.15 Arbitrage
Problem 4.16 Booster Placement
Problem 4.17 Maximum Tape Utilization Ratio Problem 4.18 Task Scheduling
Problem 4.19 N-nary Huffman Codes
Problem 4.20 N-nary Huffman Code Variations Problem 4.21 Interval Intersections
Problem 4.22 Task Scheduling
Chapter 5 Backtracking
Problem 5.1 Subset Sum
Problem 5.2 Minimum Length Board Arrangement Problem 5.3 Minimum Weight Machine Design Problem 5.4 Maximum Preferences
Problem 5.5 No Separation Dictionary Problem 5.6 No Sum Sets
Problem 5.7 Instant Insanity
Problem 5.8 Integer Transformation
Problem 5.9 Latin squares
Problem 5.10 Jewel Arrangements
Problem 5.11 Latin squares with Repetition Problem 5.12 Maze of Romeo and Juliet Problem 5.13 Work Assignment
Problem 5.14 Hi-Q
Problem 5.15 Pentominoe Configuration Problem 5.16 Board Permutation
Problem 5.17 Optimal Scheduling
Problem 5.18 Computation without Priority Problem 5.19 Museum Guards
Problem 5.20 Unique Museum Guards
Problem 5.21 Tribe Troops
Problem 5.22 Corroded Expressions
Problem 5.23 Complete Circle Sequences Problem 5.24 Discrete 01 Strings
Problem 5.25 Painting Robots
Problem 5.26 n2-1 Puzzle
Chapter 6 Branch and Bound
Problem 6.1 Minimum Length Board Arrangement
Problem 6.2 Minimum Length Board Arrangement Problem 6.3 Minimum Weight Vertex Cover Problem 6.4 Maximum Cut
Problem 6.5 Minimum Weight Machine Design Problem 6.6 Maximal Preferences
Problem 6.7 n Queens
Problem 6.8 Circle Permutation
Problem 6.9 Board Permutation
Problem 6.10 Optimal Scheduling
Problem 6.11 Computation without Priority Problem 6.12 Museum Guards
Problem 6.13 Knight’s Tour
Problem 6.14 Push Box
Problem 6.15 Graph Transformation
Problem 6.16 Row and Column Transformation Problem 6.17 n2 Puzzle
Problem 6.18 The Most Distant State Chapter 7 Randomized Algorithms
Problem 7.1 Modular Square Roots
Problem 7.2 Set Equality
Problem 7.3 Inverse Matrix
Problem 7.4 Multiplication of Polynomials Problem 7.5 Queen Control
Problem 7.6 3SAT
Problem 7.7 Combat Vehicles
Problem 7.8 Circle Permutation
Problem 7.9 Knight’s Control
Problem 7.10 Attacking Knights
Chapter 9 Approximation Algorithms
Problem 9.1 Approximation Algorithm for TSP
Problem 9.2 Approximation Algorithm for SAT
Problem 9.3 Approximation Algorithm for MAX-SAT Problem 9.4 Approximation Algorithm for Subset Sum Problem 9.5 Polynomial Approximation for Subset Sum Problem 9.6 Linear Time Implement of greedySetCover Problem 9.7 First Fit Bin Packing
Problem 9.8 Best Fit Bin Packing
Problem 9.9 First Fit Decreasing Bin Packing
Problem 9.10 Best Fit Decreasing Bin Packing
Problem 9.11 Next Fit Bin Packing
Chapter 10 Algorithm Optimization
Problem 10.1 Goods Shipping
Problem 10.2 Pebble Merging
Problem 10.3 Max-cost Goods Shipping
Problem 10.4 Pentagons
Problem 10.5 Shortest Path of Interval Graphs
Problem 10.6 Shortest Path of Circular Interval Graphs Problem 10.7 Two Processor Scheduling
Problem 10.8 Off Line Min
Problem 10.9 Nearest Common Ancestors
Problem 10.10 Darwin Chips
Problem 10.11 Multi-peg Tower of HANOI
Problem 10.12 Linear Time Huffman Algorithm Problem 10.13 One Processor Scheduling
Problem 10.14 Max Cost One Processor Scheduling Problem 10.15 Airplane Refueling
Chapter 11 On Line Algorithm Design
Problem 11.1 Off Line Paging
Problem 11.2 LRU On Line Paging
Problem 11.3 k-server Problem
Midterm Exam 1
Problem 1 Maximum Sequence Differences Problem 2 Bitonic Tours
Problem 3 Optimal Scheduling
Midterm Exam 2
Problem 1 Pebble Merging
Problem 2 Integer Factorization Problem 3 Oiling Car
Final Exam 1
Problem 1 Multiplication Table Problem 2 Work Assignment
Problem 3 Pilot Match
Final Exam 2
Problem 1 k Median of Line
Problem 2 Graph Transformation Problem 3 Maximum Cut