CSS 443- Advanced
Programming Methodologies
Computing and Software Systems
Name:
|
Office Hours: Mon/Wed Or by appointment Office: Room UW1-339 |
We
will be learning:
In this course, we will examine algorithms from both theoretical and practical application aspects. From theoretical aspect, we will learn the approaches to analyze and design algorithms. We will first review the necessary mathematics, which include a review of basic algebra, learning the asymptotic notation, and learning the approaches to solving recurrences. We will use this knowledge to review and analyze the operations on the data structures we have learned previously. We will also learn two-dimensional searching algorithms, and analyze these algorithms based on the newly acquired mathematics tools. After which, algorithm-designing methodologies including divide and conquer, dynamic programming, and greedy algorithms will be studied in detailed. We will practice the theories learned by solving practical problems in the form of programming assignments. If time allows, we will apply the algorithm designing and analyzing approaches learned to specific application domains (e.g. Computational Geometry, Matrix Operations, etc.).
You should be familiar and fluent with basic data structures (arrays, lists, queues, stacks, trees, hash tables), and simple sorting algorithms (e.g. bubble sort, quick sort, heap sort, etc.). By fluent with data structures I mean, you are experienced with implementing the basic operations manipulating these structures. For example, insert/delete from singly/doubly linked lists, en/de-queue, implementing stack using lists or arrays, traversing different types of trees, hashing functions, collision resolution, etc. Please let me know if you are not comfortable with any of the above.
Prerequisites: CSS 343.
Required
Text:
Required Text: Introduction to Algorithms Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, McGraw-Hill, 2001.
Grading:
Final Exam 25%
Mid
Term Exam 20%
Homework Assignments (approx. 2) 10-20%
(depending on schedule)
Programming Assignments (approx. 4) 35-45% (depending on schedule)
Class
Attendance and Lecture notes:
Attendance is not required. The materials covered in the lectures are taken mainly from the recommended textbook. When required, I will hand out extra reading materials. When necessary I will also hand out printed lecture notes (whenever possible, in advance) to help you follow the lectures. These notes only summarize the main concepts. The lecture notes are not meant to be and should not be treated as a substitution for the textbook/reading materials. Lecture notes are designed to help you read the text. Without reading the text, it is very likely that you will not be able to follow the subsequent lectures. Ultimately, in the exams/homework, you are responsible for what is covered in the lectures/textbook/reading materials.
Schedule:
Week
|
Topics
|
|
Date
|
NOTE: |
|
1 |
Introduction
Linked List and
Collecting Garbage
|
1 10(p200-213) |
Mar 31 Apr 2 |
Assign: MP #1 |
|
2 |
Programming with Threads |
Extra Handouts |
Apr 7, 9 |
Due: MP #1 Assign: MP #2 |
|
3 |
Sort and Asymptotic Notation: Q, O, W Recurrences and applications |
2, 3 (p. 15-57) 4 (p62-75) |
Apr 14, 16 |
|
|
4 |
Recurrences and applications Review and Analyze: Heap Sort, Quick Sort, etc |
6,8,9 (all) 7(p145-155) |
Apr 21, 23 |
|
|
5 |
Application: 2D Search with Uniform Grid |
Extra Handout |
Apr 28, 30 |
Due: MP #2 Assign: HW #1 |
|
6 |
Catch up Mid Term Exam |
|
May 5, 7 |
Due: HW #1 |
|
7 |
Application: 2D Search with Quad/k-d Tree |
Extra Handout |
May 12, 14 |
Assign: MP #3 |
|
8 |
Design: Dynamic Programming |
15(p321-356) 16(p 371-388) |
May 19, 21 |
|
|
9 |
Memorial Day (No Class) Design: Greedy Algorithms |
17 (all) |
May 26, 28 |
Due: MP #3 Assign: HW #2 |
|
10 |
Catch up Final Exam Review |
|
Jun 2, 4 |
Due: HW #2 |
|
11 |
Final Exam |
|
Jun 9 |
|
|
|
|
|
|
|
General
Policies:
Assignment Deadlines: There will be no late assignments accepted. Let me put this in another way, there will be no late assignments accepted. These apply to both homework and programming assignments. Pay attention to the deadline on the assignments (including the time), there will be no late assignments accepted. Let me explain this again, there will be no late assignments accepted. I am actually a reasonable person, come talk to me about exceptional circumstances.
Lateness to classes: It does not bother me, just don’t disturb anyone. On the days the homework assignments are due, the due time will be 10 minutes after class time. So you may wish to make sure you are not more than 10 minutes late for those classes. If you want to leave early, it would be very nice if you could give me advance warning. If that’s too much trouble, or if you forgot, don’t worry, just don’t disturb anyone and leave quietly.
Commitments and such: I am usually very easy going. I like relaxed classrooms for learning and will try my best to create such an environment. Please do not confuse relax environment with relax requirements. I work very hard, and expect students to work as hard. On average, each percentage of your assignments should represent one-two hours of outside-of-class time. Please use this as a reference and let me know if you are spending too much time on the assignments. If most of you are experiencing the same problem, then we will have to adjust the amount of work. Please seriously consider if you have the time this quarter for this class. If you do have the time, please stay in this class, I will work very hard and try my best to make this class a worthwhile learning experience for you.
Collaboration: You are expected to do your own work, including programming assignments and homework assignments. Discussions of problems with fellow students are ok, provided you do not exchange algorithms, or copy code. You may always discuss any problem with me. You are expected to subscribe to the highest standards of honesty. Failure to do this constitutes plagiarism. Plagiarism includes copying assignments in part or in total, debugging computer programs for others, verbal dissemination of algorithms, and results, or using solutions from other students, solution sets, other textbooks, etc. without crediting these sources by name. Plagiarism will not be tolerated in this class, any more than it would be in the “real world”. Any student guilty of plagiarism will be subject to disciplinary action[1]. In the “real world”, you are responsible for the security of your intellectual properties. In our case, you are responsible for the security of your source code (either on public hard disk, or on printed copies). Remember to erase your work from all public hard disks, and to dispose the hard copies of your source code with care. If someone did not break any law, and has identical solution as yours, you are a suspect of plagiarism.
Programming
Assignments:
Submitting Source Code: You will submit your source code of each programming assignment (or
machine problem, or mp) and I will compile/run/test your submissions. Here are
the details: we have a class folder located at: \\Hermes\Classes\CSS443\. Before the due time of
each mp, a folder with the corresponding mp number will be created here (e.g.
mp1, mp2, etc.). Before the due time of the assignment, you should:
For example, for mp1, I will create a zip file “KelvinSungMP1.zip” containing all the relevant source files to my mp1 solution and copy this file to \\Hermes\Classes\CSS443\mp1\. There is TestFolder located in \\Hermes\Classes\CSS443\. You should try copying a simple zip file over and make sure everything works. DO NOT wait for the first mp submission to try this, on the due date of the mp, the corresponding directory will be close at precisely the due time. After which, you will not be able to submit your work! There will be no exceptions! If there is an emergency and/or personal difficulty, please talk to me in person. I will not accept submissions via emails. You are responsible to ensure that the files you submitted are correct. Submit as many solutions as you like, I will only look at the last one received before the deadline. Please do not submit hard copies of your source code. Let’s try to safe some trees. I will read your submitted code on-line. Remember to document your code, and practice the good programming skills you learned in CSS 343. You will be graded on your programming styles (~5%)
Submitting Design Document: When requested, you must also submit the pseudo code of the algorithm you have implemented, and a detailed analysis of the run time of your algorithm. Please submit hard copy of this documentation (~25%) in class on the due date. Once again, PLEASE DO NOT submit hardcopies of your source code.
Grading: Your programming assignments will be graded based on two major criteria: correctness (~35%) and efficiency (~35%). If your program does not compile or does not produce any output, you will not receive more than ~30% of the allocated credit. If your program is based on an inefficient algorithm, you will not receive more than ~65% of the allocated credit even if it runs correctly. The above given percentage are for your reference. In an actual assignment, these numbers may vary. Please pay attention to the actual credit distribution in each programming assignment and plan accordingly.
Special
Needs
If you have a disability and wish to discuss academic accommodations, please contact Kathleen Bernhard (425-352-5307) at Student Affairs as soon as possible. I will coordinate with the University to ensure that the appropriate accommodations are made in this class.
Problems
If you have any problem with this course, please come talk to me as soon as possible. I would like to help in anyway I could, but I have to know there is a problem. If you should fall behind in this class, it will be difficult to catch up.
[1] This paragraph is copied in its entirety from Dr. Michael Stiber’s CSSIE-450 syllabus from Autumn of 1998.