# Algorithms

Summer 2013 offering at UT as EE w360C

In this course, we will study the design and analysis of efficient algorithms. The focus will be on fundamental design techniques such as greedy approaches, divide and conquer, dynamic programming, network flow, and randomized algorithms. We will study measuring program performance using asymptotic notation.

The principle focus of the lectures will be theoretical. In addition to the lectures and their associated homework assignments, there will be a number of programming assignments, in which you will be required to implement algorithms.

Email: | junaid.siddiqui@lums.edu.pk |

Office Hours: | Monday 1-2pm, ENS 112-B |

Email: | nokhbeh@gmail.com |

Office Hours: | Monday 4-6pm, ENS 122 |

Email: | jameszhengxi1979@gmail.com |

Office Hours: | Wednesday 2-4pm, ENS 122 |

## Course Information

Class meetings | MWF 11:30am–12:45pm, ENS 116 |

Pre-requisites | Targeted to undergraduate students who have taken a programming course and are comfortable writing code in some programming language. |

Required text | [ISBN/0321295358] |

Optional text | [ISBN/0262033844] |

#### Grading

24% | Homework assignments (8 assignments) |

16% | Programming assignments (4 assignments) |

40% | Midterm Examinations |

20% | Final Examination |

## Tentative Schedule

# | Date | Topic | Readings |
---|---|---|---|

Topic 1: Foundations | |||

Introduction, Administrivia | |||

Stable Matching | |||

Stable matching analysis and implementation | |||

Asymptotic growth | |||

Topic 1: Graphs | |||

Basic concepts and traversal | |||

Directed graphs | |||

Exam I - 10% - CPE 2.208 | |||

Topic 1: Greedy Algorithms | |||

Interval scheduling | |||

Shortest path algorithm | |||

Minimum spanning trees | |||

Implementing Kruskal’s algorithm | |||

Topic 1: Divide and Conquer | |||

Mergesort | |||

Recurrence relations | |||

Integer multiplication | |||

Fast fourier transform | |||

Exam II - 15% - CPE 2.208 | |||

Topic 1: Dynamic Programming | |||

Weighted interval scheduling | |||

Knapsack | |||

Sequence alignment | |||

Shortest Paths | |||

Topic 1: Network Flow | |||

Maximum-flow problem | |||

Flows and Cuts | |||

Bipartite matching | |||

Exam III - 15% - CPE 2.208 | |||

Topic 1: Revision | |||

Revision | |||

Revision | |||

Revision | |||

Topic 1: NP-Completeness | |||

Reductions | |||

Certifications | |||

Revision | |||

2013/8/17 |