## CS 344: Design and Analysis of Computer Algorithms - Spring 2014

**Download the course Syllabus.**

#### Topics:

We will cover a large subset of the following and possibly some new algorithmic topics and applications, as time permits:

- Mathematical tools. Review of mathematical background, concepts of algorithm design, complexity, asymptotics, induction, and randomization. Fibonacci numbers. Euclidean gcd algorithms. Universal hashing.
- Divide and conquer. Fast integer multiplication; recurrences; the master theorem; mergesort; randomized median and selection algorithms; quicksort; fast matrix multiplication.
- Sorting. Lower bounds for comparison-based sorting; binsort and radix sort.
- Dynamic programming; Paradigm of SPs in DAGs; longest increasing subsequence; approximate string matching; integer and (0,1) knapsack problems; chain matrix multiplication; single-pair reliable SPs, all-pairs SPs; independent sets.
- Graph search. Graph classes and representations; depth first search in undirected and directed graphs; topological search; strongly connected components. Breadth first search and layered DAGs.
- Shortest Paths (SPs) in digraphs. Single-source SPs for nonnegative edge weights; priority queues and Dijkstra; SPs in DAGs; single-source SPs for general edge weights. Maximum adjacency search.
- Greedy algorithms. Spanning trees and cuts, analysis of union-find and path compression; MST algorithms; randomized algorithm for global minimum cuts; approximate set cover.
- Network flows. Max flow min cut theorem and integrality; fast algorithms; disjoint (s,t)-dipaths; maximum bipartite matching & minimum vertex cover. Global minimum cuts.
- Elements of NP-completeness & problem reductions.
- NP-hard problems. Search and selected approximation algorithms.

#### Tentative Calendar

Check Rutgers' Key Dates.

- Lecture X - Jan. 22: Cancelled due to weather
- Lecture 1 - Jan. 24: Introduction to Concepts of Algorithmic Design + Complexity of adding 2 n-bit numbers

Reading material: Chapters 0, 1.1 from DPV, Chapters 1-3 from CLRS2 - Lecture 2 - Jan. 29: Number Theoretic Algorithms: Complexity of adding and multiplying 2 n-bit numbers, modulo arithmetic

Reading material: Chapters 1.1,1.2,1.3,1.4 from DPV, Chapter 31 from CLRS2 - Lecture 3 - Jan. 31: RSA Cryptosystem, , Fermat's Little Theorem and Modular Exponentiation

Reading material: Chapters 1.3,1.4 from DPV, Chapter 31 from CLRS2 - Lecture X - Feb. 5: Cancelled due to weather
- Lecture 4 - Feb. 7: Greatest Common Divisor algorithms: Euclid's test, Modulo Multiplicative Inverse

Reading material: Chapter 1.3 from DPV, Chapter 5 from CLRS2 - Lecture 5 - Feb. 12: Primality Testing and Universal Hashing

Reading material: Chapter 1.5 from DPV, Chapter 11 from CLRS2 - Lecture 6 - Feb. 14: Divide and Conquer Algorithms and Recurrence Functions, Mergesort

Reading material: Chapters 2.1-3 from DPV, Chapters 2,4,6 from CLRS2 - Lecture 7 - Feb. 19: Quicksort, Lower bounds for comparison-based sorting, Computing Medians and Other Order Statistics

Reading material: Chapters 2.3-2.4 from DPV, Chapter 7-9 from CLRS2*First homework due* - Lecture 8 - Feb. 21: Linear-time Sorting Solutions

Reading material: Chapters 2.3-2.4 from DPV, Chapters 8 from CLRS2 - Lecture 9 - Feb. 26: Greedy Algorithms: Huffman encoding, Horn formulas

Reading material: Chapters 5.2-5.4 from DPV, Chapters 16 from CLRS2 **First midterm**- Feb. 28- Lecture 10 - Mar. 5: Greedy Algorithms: Set Cover - Intro to Dynamic Programming: Chain-Matrix multiplication,

Reading material: Chapters 5.4, 6.2-6.5 from DPV, Chapter 15, 16 from CLRS2 - Lecture 11 - Mar. 7: Dynamic Programming: Longest Common Subsequence

Reading material: Chapters 6.4 from DPV, Chapter 15,22 from CLRS2 - Lecture 12 - Mar. 12: Knapsack - Introduction to Graphs, Graphs: Depth First Search and (Strongly) Connected Components

Reading material: Chapter 3.1-3.2-3.4 from DPV, Chapter 22 from CLRS2 - Lecture 13 - Mar. 14: Knapsack - Introduction to Graphs, Graphs: Depth First Search and (Strongly) Connected Components

Reading material: Chapter 3.1-3.2-3.4 from DPV, Chapter 22 from CLRS2*Second homework due* **Spring Break**- Mar. 17 to 21- Lecture 14 - Mar. 26: Breadth First Search, Single-Source Shortest Paths - Dijsktra

Reading material: Chapter 4.1-4.4-4.7 from DPV, Chapter2 22, 24 from CLRS2 - Lecture 15 - Mar. 28: Breadth First Search, Single-Source Shortest Paths - Dijsktra

Reading material: Chapter 4.1-4.4-4.7 from DPV, Chapter2 22, 24 from CLRS2 - Lecture 16 - Apr. 2: Bellman-Ford algorithm and All-Pair Shortest Path (Floyd-Warshall)

Reading material: Chapter 4.6, 4.7, 6.6 from DPV, Chapters 24, 25 from CLRS2 - Lecture 17 - Apr. 4: All-Pair Shortest Paths (Johnson's algorithm)

Reading material: Chapter 6.6 from DPV, Chapter 25 from CLRS2*Third homework due* -
**Second midterm**- Apr. 9 - Lecture 18 - Apr.11: Minimum Spanning Trees, Kruskal's and Prim's algorithms - Disjoint Sets Data Structure

Reading material: Chapter 5.1 from DPV, Chapter 21,23 from CLRS2 - Lecture 19 - Apr. 16: NP-hard Problems, NP-Completeness and Reducability

Reading material: Chapter 8.1, 8.2, 8.3 from DPV, Chapter 34 from CLRS2 - Lecture 20 - Apr. 18: Reducability examples

Reading material: Chapter 8.3 from DPV, Chapter 34 from CLRS2 - Lecture 21 - Apr. 23: Coping with NP-hard problems

Reading material Chapter 9 from DPV, Chapter 35 from CLRS2 - Lecture 22 - Apr. 25: Coping with NP-hard problems

Reading material: Chapter 9 from DPV, Chapter 35 from CLRS2 - Lecture 23 - April 30: Linear Programming

Reading material: Chapter 7.1,7.2 from DPV, Chapters 26,29 from CLRS2 - Lecture 24 - May 2: Linear Programming and Review session

*Fourth homework due: April 22*

Reading material: Chapter 7 from DPV, Chapter 29 from CLRS2*Fifth homework due*

**Final Exam: 4:00 PM - 7:00 PM May 13, 2014**

#### Prerequisites

Courses:

- CS 112 Data Structures
- CS 206 Introduction to Discrete Structures II

We assume (and briefly review early on in the class) elements of discrete mathematics, such as logarithms, proofs by induction, series and sums, permutations, asymptotics (big-Oh, big-Omega notation), basics of solving recurrences, as well as concepts of programming and data structures, e.g., linked lists, stacks, queues, trees, binary search, recursion, hashing, priority queues, graph algorithms, sorting.

#### Reading Material

The class will primarily draw upon material from the following book:

- "Algorithms" by Dasgupta, Papadimitriou & Vazirani, McGraw Hill, 2008.

The following book may also be used as references:

- "Introduction to Algorithms" by Cormen, Leiserson, Rivest & Stein, McGraw Hill (The chapters in the calendar below refer to the 2nd edition)

The books are not required for the class. Students are expected to take notes during the presentation of the material in the classroom and the recitations. Homeworks and exams will be based on the presented material.

#### Exams

There will be three exams: two midterms and one final. The first midterm will cover the material of the first third of the course, and the second midterm will cover the second third of the course. The final exam will cover material from the entire class. Check the tentative schedule above for updates. All exams will be in-class on a date arranged and announced ahead of time.

A missed exam draws zero credit. Emergencies will be considered upon submitting a University-issued written verification to the Instructor; for assistance contact your Dean's Office. Also, check the definition of Final Exam Conflicts by SAS.

#### Homework Assignments

There will be 4 to 5 sets of homework problems. You will be informed in advance when an assignment is due. A tentative scheduled is available above. The homework sets consist of practice questions which are intended to assist students in mastering the course content. They may also potentially involve limited programming effort.

Homeworks should be completed by teams of students - three at most. No additional credit will be given for students that complete a homework individually. Please inform Athanasios Krontiris about the members of your team (email: ak979\AT\cs.rutgers.edu).

Students will receive 10% extra credit if they typeset their report using LaTeX or 5\% extra credit if they typewrite their answers (e.g., using Word). Submit only PDF documents. For instance, if a pair was to receive a score of 62/100 and they typeset their report, then their score will be 68/100, i.e,. they receive a bonus of +10\% of 62 points. Resources on how to use LaTeX are available below.

#### Submission Rules

No late submission is allowed. If you don't submit a homework on time, you get 0 points for that homework. The deadline will typically correspond to the beginning of a lecture. Students can submit their homeworks electronically via Sakai.

#### Grading System

The final grade will be computed according to the following rule **(this is tentative and can change)**:

final grade = max(Case A: With Homeworks, Case B: Without Homeworks)

Case A: With Homeworks

- Homeworks: 25 points total
- First midterm: 25 points
- Second midterm: 25 points
- Final exam: 25 points
- Participation: +/- 5 points (this is up to the discretion of the instructor and the TAs)

Case B: Without Homeworks

- First midterm: 30 points
- Second midterm: 30 points
- Final exam: 40 points
- Participation: +/- 5 points (this is up to the discretion of the instructor and the TAs)

On any assignment (homework or exam), you can either attempt to answer the question, in which case you will receive between 0 and 100% credit for that question, or you can write "I don't know", in which case you receive 25% credit for that question. Leaving the question blank is the same as writing "I don't know." You can and

will get less than 25% credit for a question that you answer erroneously.

Finally, the first exam is a make-or-break situation. If your score on the first exam is 26% or less (which amounts to a blank exam) then you fail the class. The first exam will be early enough for you to drop the class.

Your participation grade can be positive or negative. By default your participation grade is 0..., e.g., if you typically come to the lectures/recitations but you rarely answer questions during the lectures or the recitations, your participation grade will be 0. Positive participation grades will be given to students that actively participate in lectures and recitations. You can also receive a negative participation grade depending on the level of your involvement in the course lectures and recitations (or lack there of) or because of issues related to collusion or cheating in homeworks and exams.

The mapping of scores to letter grades will be determined at the end of the semester. As a **rough** guide, the following rule may be used for the final grade **(it will be adapted close to the end of the semester)**:

- A: > 89
- B+: 80-89
- B: 70-79
- C+: 60-69
- C: 50-59
- D: 40-49
- F: less than 40

Students interested in a recommendation letter by the instructor will be offered one only if they achieve a score above 95 after the completion of the course.

#### Questions about Grading

If you have a question or complaint regarding the points you received on specific parts of a HW assignment, or an exam, staple a sheet of paper on the graded item, stating specifically but very briefly what parts of that document you wish to have reviewed and forward it to Athanasios Krontiris, who will handle the process of communicating with the instructor and the other TAs. Please refrain from verbal arguments about grades with the instructor or with any of the TAs. We will try to get back to you within two weeks. The deadline for submitting such requests is the last lecture.

#### Academic Standards

Exams are to be treated as individual efforts. Homeworks are not to be treated as collective efforts beyond the participation of the team members! Discussions are not allowed on how to solve specific questions in homeworks. Do not discuss assignments with students that are not currently taking the class.

A severe penalty will be given to any assignment which indicates collusion or cheating. The usual penalty for cheating on an assignment or an exam is failure in the course. At a minimum your participation grade will be influenced negatively. Stealing another person's listing or having another person "ghost write" an assignment will be considered cheating.

Turning in work without properly citing the sources of the content included in your work is plagiarism. All kinds of sources are included in this definition, even those downloaded from the web, in which case an operable link must be cited. Plagiarism from the web or other sources is considered cheating and has the same effects. Even with a reference, submitting an answer to a homework question, verbatim from any source and without any contribution on your part, draws zero credit.

You should carefully study the website of Rutgers University on Academic Integrity and the corresponding policy, as well as the corresponding policy from the department of Computer Science. Your continued enrollment in this course implies that you have read these policies, and that you subscribe to the principles stated therein.

### Latex Resources

General info on what you can do with LaTeX:

Getting Started with Latex

The Not So Short Introduction to Latex

Comprehensive List of Latex Symbols

Latex for Logicians

The first link describes many alternatives that are available for installing Tex on a Mac. The second link forwards to the MacTex package, one of the alternatives mentioned in the first website. MaxTex provides everything that you need to use Latex on Mac except from a text editor. It is, however, compatible with a wide variety of popular editors (e.g., Alpha, BBEdit, Emacs, VIM, iTeXMac, TeXShop). Note that MaxTex is a large package.

Carbon Emacs has been succesfully tested with MacTex. After installing MacTex, it is possible to directly compile and view *.tex files from Carbon Emacs's UI.

Note for Mac users: You will probably have problems previewing your PDF output when using the postscript images provided by the instructor for developing the notes. Nevertheless, the PDF file can be printed properly. Prepare your document without the images and then add them. You will probably still be able to preview the intermediate .dvi output file with the "xdvi" program.

Linux (Ubuntu)

Latex on Ubuntu

Tex Live

You just have to download and install the proper packages described above (e.g., through apt-get), use your favorite editor (e.g., emacs) to prepare a *.tex file and then you compile (run at least two times: "latex filename.tex") to get the *.dvi output. You can go from dvi to postscript with the command "dvips" and you can convert postscript to pdf with the command "ps2pdf".

Windows

Latex for Windows help

MikTex (Latex for Windows)

If you follow the instructions on the first link you should be able to get it working on a Windows system.

Below you can find Windows executables (32 bit) for the following programs (follow the order when installing):

MiKTeX

Ghostscript

Ghostview

WinEdt