SUBJECT  INTRODUCTION

 

 

COMP 3121 Algorithms and Programming Techniques

 

COMP 9101 Design and Analysis of Algorithms

 

§

 

COMP 3821 Extended Algorithms and Programming Techniques

 

COMP 9801 Extended Design and Analysis of Algorithms

 

 

 

Lecturer in Charge:                       Aleksandar Ignjatovic

 

Offered:                                            Semester 1, 2010

 

 

 

OBJECTIVES

 

Courses COMP 3121/3821/9101/9801 are about problem solving. Before you can start programming, you must first solve the problem at hand.  Thus, we will not just go over a cookbook of some well-known algorithms that you have to memorize and just learn how to implement.  Instead, we will learn how to design new algorithms for solving new problems, using various design techniques (greedy, dynamic programming, divide and conquer, etc). We will also learn how to estimate efficiency of algorithms.  To improve our problem solving skills, we will also practice by solving a few puzzles.  You will have no puzzles on the exams, but they are important and integral part of the courses.

 

Extended courses COMP 3821/9801 are intended to provide additional depth for students who might find the “regular” version of our courses insufficiently challenging. Additional material for COMP 3821/9801 will be covered in an extra lecture a week. Extended courses also include some additional and harder assignment problems that require a bit more of inventiveness.  They are strongly recommended for students interested in pursuing R&D (Research and Development), either in academia or in industry.

 

Among the well-known algorithms that use the same technique we will always choose to study those that are most frequently used in practice, in various fields, even if this requires a bit of extra work. For example, we will demonstrate the “divide and conquer” technique by studying the FFT, the Fast Fourier Transform, which reigns in DSP (digital signal processing), in digital telecommunications and in countless other fields. We will also study string-matching algorithms; one can use them to search for a particular gene on a piece of DNA.

 

COURSE TEXTBOOK, LECTURE NOTES ETC.

 

You will get detailed lecture notes for the first part of the course ONLY.  Lecture notes MUST NOT replace reading the textbook, otherwise I’d be spoon feeding you, and that is the worst “favor” I can do for you.   For COMP3121 and COMP9101 we will use “the Bible” of the field:  Introduction to algorithms, (the Third or Second Edition preferably), by Cormen, Leiserson, Rivest and Stein, The MIT Press, available at the UNSW book store.

 

I  expect you  to read the assigned chapters from the Introduction to algorithms  text book (which I will follow very closely).

 

NOTE: I cannot put the solutions of the homework problems on the web page. Instead, you must come to the lecture to hear detailed solutions or you can ask your tutor to explain the solution during the consultation hours in case you miss the class or have any additional questions.

 

We will cover only a small selection of chapters from the textbook. After you pass this course you will probably decide not to sell (or burn) this book because it is an excellent reference book for practicing programmers.

 

 

GRADING:

 

There will be regular biweekly assignments, a midterm and a final.

 

Extended classes will have the same homework assignments and same exam problems, plus some additional problems, both for the homework and on the exams.

 

Here are the weights:

 

Biweekly homework                                                                                    20%

Midterm                                                                                                         40%

Final                                                                                                               40%

 

You are strongly encouraged to do your homework yourself, because only this way you will prepare for the in-class tests. All of the problems on the tests will be solvable using reasonable modifications of the techniques you will have used  in solving homework problems. However, you can consult your colleagues, you can ask me or a tutor for advice how to solve a problem, and we will give you lots of help. Thus, if you practice through the homework and the practice tests, you should have no trouble on the exams whatsoever. The main purpose of the homework is to give you a feedback how well you understand the material.

 

Your exams will consist exclusively of design problems. You will NOT be tested for any particular knowledge, but only for the skill level you have acquired, because teaching you how to solve design problems is the objective of this course. If you plan not to work hard on homework yourselves, you are doomed – simply you will not be able to master the skills to pass the tests – this is possible only through long term practice. If you wait till the last week – you might save yourself some future frustration now and drop the class.

 

Homework solutions can be written either using the pseudo-code from the textbook or in plain English, and will not involve programming, just LOTS of problem solving to develop good design skills.

 

You MUST e-mail your homework solutions from your CSE account ONLY, otherwise they will not be graded. Late homework is accepted ONLY with a good reason. The midterm and the final will be closed book. The grade will be determined as a correspondingly weighted sum of the homework, the midterm and the final scores.

 

Teaching Philosophy: Zen-Buddhism with elements of Nietzsche and John Cleese.

 

 

 

Topics to be covered in COMP 3121/9101 include*:

*COMP 3821/9801 cover the same topics but in greater depth

Introduction:

 

·        Please review the basic material from my little review manual.

 

Methods for Algorithm Analysis

 

·        Asymptotic behavior, recurrences, summations, estimations;

·        The Master Theorem;

·        Applications of the master Theorem: Fast integer multiplication;

·        When should you trust asymptotics

 

Divide-And-Conquer Method

 

·        Weighing  coins

·        Multiplying polynomials and FFT

 

 The Greedy Method

 

·        Activity Selection problem;

·        When greed pays off -  foundations of the Greedy Method;

·        Discrete (0-1) Knapsack Problem;

·        Continuous (fractional) Knapsack Problem;

·        File compression: Huffman Codes.

 

Dynamic Programming Method

 

·        Assembly line scheduling;

·        Multiplying chains of matrices;

·        Foundations of Dynamic Programming;

·        Longest Common Subsequences;

·        Optimal Binary Search Trees.

 

 

Iterative Methods

 

·        Network Flow Algorithms;

·        Flow networks;

·        Ford – Fulkerson method;

·        Tricky correctness proofs: When do you really need math to see that the algorithm you designed really works;

·        Iterative methods for solving equations.

 

 

String Matching Algorithms

 

·        “Naïve” string matching algorithm;

·        Rabin – Karp algorithm;

·        Designing useful finite automata:  string matching again;

 

Intractable Problems and Approximation Algorithms

 

·        Feasibility

·        NP complete problems and NP hard problems

·        Feasible reductions

·        Approximate solutions

 

Practicing problem-solving while having fun:  Assorted Puzzles