ARCHIVED WEB SITE
Course Announcements:
Jan 08th Welcome to CPSC 319 course! This web site will be used as primary means for communication and announcements.
Please contact your TA directly for ALL questions about code, assignment specs, bonuses, extensions on assignment submission and question or clarification regarding material covered in labs.
You can find tutorial plan, assignment submission requirements, assignment submission record, code examples, etc. on TA web site.
NOTE: ALL QUESTIONS regarding assignments (specifications, code,
marking) should be directed to your TA.
You can send an e-mail or make an appointment to met him if you need any help
with your program, report or algorithm.
Algorithms
Robert Sedgewick,
Kevin Wayne
March 19, 2011
032157351X
978-0321573513
Pearson Education, 4th Edition
Recommended Reading
Data Structures and Algorithms in Java, Adam Drozdek, Brooks/Cole publishers, a division of Thomson Learning, 2001 or 2005 edition (other editions are acceptable)
Algorithms, Design Techniques and Analysis, M. Alsuwaiyel, World Scientific, 1999
Introduction to Algorithms Cormen, Lieserson, Rivest, Stein Mc Graw Hill 2001
Data Structures and Algorithm Analysis in Java Mark Allen Weiss, Peachpit Press, 1998
Java Books
It is expected that students have basic procedural and object-oriented programming skills, as introduced in the courses CPSC 219, or 231/235. Since Java is the programming languages that students were made familiar with, it is expected that students are confident in performing assignments in those languages.
The course introduces algorithms that can be used to solve several fundamental problems as well as data structures that are commonly used to manage information when solving problems of small-to-moderate size. It also uses the terminology and notation that is commonly used in computer science for the analysis of algorithms.
The course introduces basic data structures, such as sorting, searching, arrays, lists, trees, graphs and hash tables, as well as some computational problems. Students are required to write programs using the above algorithms and data structures on assignments, to perform experiments involving the execution of their programs on data sets in order to assess the performance of their algorithms, and to use very simple analytic techniques to assess the performance of simple fragments of code.
Please note that learning to program is a very time-consuming activity and assignments in this course may well take more time to complete than assignments in other courses. The course emphasizes student activity. This means that a significant portion of what you learn will come from working on the assignments and programming independently.
History of Algorithms. Data Structures.
Lecture on History of Algorithms
Complexity. Algorithms. Textbook Chapter 1.4
Lecture Analysis of Algorithms
Search. Sorting. Bubble sort, Insertion Sort, Selection Sort. Textbook Chapter 2.1
Lectures Searching Applications, Elementary Sorts
Merge sort, Quick Sort textbook Chapters 2.2, 2.3
Notes: simple sorts, complex sorts
Arrays. Lists.
Lectures Mergesort, Quicksort
Week 5
Stacks. Queues. Binary Trees. Textbook Chapters 1.3, 2.4, 3.2
Lecture Stacks and Queues
Data Analysis lecture
Week 6
Binary
Search Trees. AVL trees. Textbook Chapter 3.2.
Lecture Binary Search Trees
Week 6 - READING WEEK, NO CLASSES
Midterm exam review questions.
Midterm Exam.
Week 8
Lecture on kd trees
Heaps. Heapsort. Textbook Chapter 2.4
Lecture Priority Queues
Week 9
Hashing. Lecture on hashing.
Perfect hashing.
Coalesced hashing lecture.
Textbook Chapter 3.4
Lecture Hash Tables
Week 11Graphs
Textbook Chapters 4.1, 4.2
Lectures Undirected Graphs, Directed Graphs
NP-complete comic, Graph comics
Graphs. Prim's, Kruskal's, Dijkstra algorithms
Textbook Chapters 4.3, 4.4
Graph review questions and corresponding Graph review figures
Greedy Algorithms lecture
Lectures Minimum Spanning Trees, Shortest Paths
Week 12
Invited lectures
Week 13
Applications of algorithms. Image Processing, biometrics, computer simulation.
Wednesday: Industry Invited lecture: "How to get hired by industry" James Birchall, Pason Systems, Calgary
Final review. Last week of classes.
Week 14
April 14th, Monday - FINAL TUTORIAL Q&A SESSION ORGANIZED BY YOUR TAs.
Three components are included in the determination of the course grade.
| Component | Component Weight |
| Assignments | 30% |
| Midterm Examination | 30% |
| Final Examination | 40% |
The lab work and assignments are considered to be essential components of the course. Completed assignments should be submitted electronically to your TA. Remember to put your name, tutorial section and your TA's name on any material you hand in.
There will be four programming assignments in this course. Each assignment is to be submitted on the due date. Each of the FOUR assignments must be submitted in order to pass the course!
Please consult your TA web site on late submission policies and exceptions.
IMPORTANT: Versions of assignments that you find on this web page MAY be modified by your instructor at a later date, but no later than 3 weeks before the assignment is due.
NOTE: For Engineering students, Java is taught concurrently with CPSC 319 course. It is the primary language for all assignments. However, request to use another language (C++) will be honored by your TAs for each individual assignment upon e-mail request. Submission procedures will be explained by your TAs.
Assignment late submission policy:
Submitting your assignments is MANDATORY to pass this course. In case you cannot complete it on time, you can ask extension from your TA for up to 2 days (via e-mail), with each day penalty of 10% of your final assignment mark will be assessed.
Submission instructions:
Assignments are to be submitted through D2L system. Each student will find one folder in his/her D2L account to submit the assignment in, and notification will be sent to your TA once you upload your files in the folder.
Go to ASSESSMENTS --> Dropbox and submit your assignment in
the folder called Assignment 01 - <Your Tutorial No>.
The convention for your enclosed file (zip, z7 or rar) should be: Tutorial-No_Last-Name_Assignment-No,
for example (T02_Jarada_01).
Asmt 1 Sorting and Searching
Asmt 2 Binary Search Trees
Asmt 3 Hashing
Asmt 4 Graphs
Each of you has been assigned two labs per week. TAs will provide help with the assignments. Since TAs for this course spend most of their required time in the lab, you should go to the lab for help rather than seeking out TAs in their offices.
If you encounter problems in the lab that your TA can not resolve, or if you want to discuss the operation of the labs, please contact the Instructor. You should contact your Instructor to discuss lectures, exams and the overall organization of the course. In this course, you are always welcome to ask questions if you don't understand something during the lecture or in the lab. You can also always contact your instructor during office hours or any time by e-mail. Some of the exercises and assignments may require a reasonable amount of time to complete. You will find that you need to spend time on the computer outside of your regularly scheduled labs, and this is the way the course is designed.
Some lectures:
See notes from CPSC 319 course on simple sorts,
complex sorts,
hashing, trees
History of Mathematics
Trees
Hashing and compression
Department of Computer Science
University of Calgary
2500 University Dr. N.W.
Calgary, AB, T2N1N4
Office: MS 269