Course Textbook

Title: "Data Structures and Algorithms in Java"
Author: Adam Drozdek
Publisher: Brooks/Cole publishers, a division of Thomson Learning, 2001

Recommended Reading

1. Algorithm Analysis in Java
   Mark Allen Weiss, Peachpit Press
2. Robert Sedgewick,
   Michael Schidlowsky, Addison Wesley Professional
3. Fundamentals of Algorithmics,
   Giles Brassard and Paul Bratley, Prentice Hall
4. Algorithms, Design Techniques and Analysis,
   M. Alsuwaiyel, World Scientific
5. Algorithmics: Theory and Practice,
   Giles Brassard and Paul Bratley, Prentice Hall

Books on Java

  1. Java by Dissection by Ira Pohl and Charlie McDowell

  2. Java Programming from the beginning K.N. King, Norton and Company

  3. Java - A Framework for Programming and Problem Solving K. Lambert, M. Osborne Brooks/Cole

Course Information

Computer Science 331 Information Structures I

Algorithms: searching, sorting, graph navigation. Data structures: arrays, lists, stacks, queues, graphs, trees, hash tables; time and space efficiency of associated algorithms.

Objectives and Outcomes

It is expected that students have basic procedural and object-oriented programming skills, as introduced in the prerequisite courses CPSC 231 and CPSC 233. CPSC 331 continues CPSC 231 and 233 by introducing additional tools and skills that are needed to solve problems by computers, through the development of programs with high-level programming languages. It 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 introduces the terminology and notation that is commonly used in computer science for the analysis of algorithms.

The course introduces fundamental data structures, including arrays, linked lists, graphs, trees, and hash tables. For each of these, the course includes definitions of the operations on data that these data structures support, algorithms that are commonly used to implement these operations, and a discussion the worst-case complexity. The course introduces fundamental algorithms to search for data in sorted and unsorted lists, and in graphs and trees, as well as algorithms to sort the elements of an array. This course also introduces terminology and notation that is commonly used in computer science to describe the worst-case performance of algorithms on large inputs.

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 large sets of data 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.

Course Outline

Week 1

   Week 2

                             Time and space complexity
                             Big-O notation
                             Examples of iterative and recursive algorithms
                             Worst case, average, best case performance

Week 3

Week 4

Week 5

Arrays
Singly and doubly linked  lists  
Circular lists
 

Week 6

Week 7

Week 8

Week 9

Week 10

     Graph definitions and operations
     Graph traversals
 

Week11

Week 12

Week 13

Course Evaluation

Three components are included in the determination of the course grade.

Examinations

 The final exam will be scheduled by Registrar during the final examination period.

Labs

The lab work and assignments are considered to be essential components of the course. Completed assignments should be deposited in the appropriate box for your lab section located on the second floor of the Math Sciences building or submitted electronically (instructions will follow). Remember to properly identify and label any material you hand in.

LAB exercises are now available. They are grouped according to subjects studies in the course.

Assignments

There will be four programming assignments in this course. Each assignment is to be submitted on the due date as indicated below. Please note that ALL assignments should be attempted in order for you to pass the course.  Late assignments will not be accepted.

IMPORTANT: Preliminary versions of assignments that you find on this web page MAY BE modified by your instructor at a later date, but no significant changes will take place within the two weeks before the assignment is due.

All assignments for this course are individual. Academic misconduct on assignments and / or exams will result in penalties which may include an F grade on the assignment component, failing the course and expulsion from the faculty and university (see Plagiarism/Cheating/Other Academic Misconduct sections of the university calendar).

Access to Computers and Help

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.

General Notes

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 lectures or labs. You can also always contact your instructor during office hours or any time by e-mail. Some 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.

Useful links

This page was last updated on 06/01/2020

Department of Computer Science
University of Calgary
2500 University Dr. N.W.
Calgary, AB, T2N1N4
Office: MS 269
Phone: (403) 220-5105
Fax: (403) 284-4707
E-mail: marina@cpsc.ucalgary.ca