Design and Analysis of Algorithms Spring 2014

Course Number: 
CSCI 6212

Design and analysis of algorithms. Turing machines; NP-Complete theory. Algorithmic techniques: divide-and-conquer, greedy, dynamic programming, graph traversal, backtracking, and branch-and-bound. Applications include sorting and searching, graph algorithms, and optimization.

The textbook is available at the campus book store. If sold out, or if you want to order it online, here are the links:
Introduction to Algorithms

Homework 1 due Monday 2014-02-03 11:59pm. Email your draft by 2014-01-29 11pm to get 5% bonus.
Explain asymptotic notation Θ, O, o, Ω and ω (total 20 points)
Each one of them must contain:

  • formal, mathematical definition (2points)
  • explanation your own words (2points)
  • graph (2points)
  • example (2points)

Homework 2 due Monday 2014-02-10 11:59pm. Email your draft by 2014-02-04 11pm to get 5% bonus.
Please submit your homework to our TA.

  • Visualize Merge Sort using an example as done in class. The array could be any size as long as it is a 2^N form. (6points).
  • Explain your observation of the running time using the visualization(6points)
  • Generalize the running time of Merge-Sort for an array of n elements (6points)
  • Affidavit that you have done the reading assignment and understood the material (2points)

Homework 3 due Monday 2014-02-17 11:59pm. Email your draft by 2014-02-12 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • In class, we proved that the running time of mergesort is T(n)=n*lg(n) under the following condition
    T(n) = 0 if n = 1
    T(n) = 2T(n/2) + n if n > 1
  • 1) Prove by telescoping that T(n) = cn*lg(n) + cn under the following condition (6points):

    T(n) = c if n = 1
    T(n) = 2T(n/2) + cn if n > 1

  • 2) Explain why T(1)'s values above 0 versus c will not matter for comparing algorithms (4points). Give an example of a hypothetical situation when you implement a search engine in terms of the search volume and execution time required to complete the search (2points).
  • 3) We have two versions of T(n) above depending on whether we use a constant c or not. Explain why the two versions of running time will not make a difference in terms of algorithm analysis using the asymptotic notation (5points).

    For T(n) = cn*lg(n) + cn, explain, in terms of growth, the condition where cn becomes insignificant and therefore ignorable in comparison to cn*lg(n) (3 points)

Homework 4 due Monday 2014-02-24 11:59pm. Email your draft by 2014-02-19 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) Explain which one you should choose Memoized-Cut-Rod() or Cut-Rod(). Defend your decision by explaining the comparative advantages. In other words, where does the time saving come from ? (5 points)
  • 2) What is the hidden cost when a recursive algorithm is implemented in a programming language ? (5 points)
  • 3) Explain when you would consider Dynamic Programming over Divide-and-Conquer approach for a problem. What would be the nature of the problem ? (3 points) Give a real-world problem where dynamic programming would be useful (2 points)
  • 4) Explain why we were able to use a) instead of b) (3 points) What is the main benefit doing so (2 points) ?
    a) max 1≤i≤n ( p[i] + r(n-i) )
    b) max 1≤i≤n ( r(i) + r(n-i) )
    Feel free to use drawings.

Homework 5 due Monday 2014-03-03 11:59pm. Email your draft by 2014-02-26 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) Compare and contrast Dynamic Programming and the Greedy Method ( 5 points ) ?
  • 2) Say an optimal solution to a activity-selection problem (p415-421) is found using the greedy method. Could dynamic programming be used for this problem ( 1 points ) ? Explain why it can/cannot be used ( 4 points).
  • 3) You can solve the fractional knapsack problem (p426) "greedily" picking up high value per pound. Can you solve the 0-1 knapsack problem the same way ? ( 1 points) Explain why you can/cannot use that method. (4 points)

Midterm Exam 2014-03-04 Open physical book/notes exam. No communications devices.

Homework 6 due Monday 2014-03-24 11:59pm. Email your draft by 2014-03-19 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) Draw the following graph (4 points)
    G = ( V, E )
    V = { a,b,c,d,e,f }
    E = { (a,b), (a,e), (c,d), (d,e), (b,d), (d,f ) }
  • 2) Draw its predecessor subgraph, G' (4 points)
  • 3) Express its predecessor subgraph G' in the same format as G above using G', V', E' ( 2 points)

Homework 7 due Monday April 7th 11:59pm. Email your draft by Friday April 4th 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) Draw the following directed graph (2 points)
    G = (V, E)
    V = { u, v, w, x, y ,z }
    E = { (u,v), (v,w), (w,z), (z,v), (v,y), (x,v), (x,x) }
  • 2) Visually show each step of the DFS algorithm's execution as done on textbook page 605 (8 points)
  • 3) Create and visually show a (max) heap using the following numbers as shown on textbook page 152 (4 points):
    3, 2, 8, 23, 10, 14, 7, 20, 1, 5, 13, 6, 1

Homework 8 due Monday April 14 11:59pm. Email your draft by Thursday April 10th 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA. If a problem was covered in class, only the classroom answer will be accepted.

  • 1) A heap is given to you in an array A[1..n]. Characterize A[1] (2 points)
  • 2) There is an array A[1..n] of integers. Would Max-Heapify(A,1) in general result in a heap ? Explain how if it would or why not if it would not ( 4 points)
  • 3) There is an array A[1..n] of integers. What would be the best execution time for outputting them in ascending order under an ideal situation when you know the characteristics of the data ? ( 4 points )

Homework 9 due Monday April 21 11:59pm. Email your draft by Thursday April 17th 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) You created a sorting algorithm. Its running time turned out to be O(n^2). How much better can you make this algorithm ? You do not know the nature of the data except the elements are of the same type. (4 points)
  • 2) Your employee delivered an algorithm for solving a task. You were told the running time is O(n^3). You have a large amount of data to run through this algorithm. Your boss wants to know how long it will take for you to run this algorithm on the entire data set. What kind of guarantees can you make to your boss ? Please use constant c if needed. (4 points)
  • 3) Your implementation of an algorithm has a running time of 9n^3 + 5n^2 -7n + 10. Your computer scientist contractor says the algorithm has Ω( n^2 ). Due to a large n,
    n = 1.2 billion, your boss wants to reduce the running time down to O(n lg n). Can you guarantee your boss the execution of algorithm within his desire timeline ? (2 points) Justify your answer. Why can you ? or why can't you ? (4 points)

Homework 10 due Monday April 28 11:59pm. Email your draft by Thursday April 24th 11pm to get 5% bonus even if incomplete as long as honest effort *is shown*. Honest effort will be judged by the TA.

  • 1) Say you are given a problem to solve. You never heard of this problem before and it does not look similar to any of the algorithms in your textbook. What steps would you take in order to solve this problem ? Provide justification for every step (4 points)
  • 2) Your boss wants time estimates on this problem. First, she wants to know how long it's going to take for you to come up with an algorithm. Second, she wants to know how long it has to run the algorithm to solve the problem. What actions would you take to answer these questions ? Demonstrate your actions using a decisions tree (or flow chart). Provide justification for each action. (6 points)

Final Exam on Tuesday, May 6, 2014 6:10pm - 8:30pm
Classroom: FNGR 207

CSCI 6212.10 final exam will be held on .

Homework 11 due Monday May 5th 11:59pm.

  • Find an interesting, real-world problems that are not mentioned in class sessions or in the textbook. Clearly state the background and the problem in English and state the sources (4 points). Use visual elements (diagrams and pictures) to illustrate the problem intuitively (4 points). Construct candidate algorithms to address the problem (4 points) and justify your approach (4 points)

Group articles

There is no content in this group.

Design and Analysis of Algorithms Spring 2014 members

jbyun