Transcript Ch. 3 Wed. 23.Sep.2015

Computer Engineering Department
Islamic University of Gaza
ECOM 3312
Data Structures and Algorithms
Undergraduate Course
Fall 2015-2016
Prof. Mohammad A. Mikki
Room
I215
Tel.
Ext. 2876
email: [email protected]
Skype id: mohammad.mikki
Homepage: http://site.iugaza.edu.ps/mmikki/
Lecture 1
Syllabus & Course Overview
Instructor
Mohammad A. Mikki
Professor of Computer Engineering
Computer Engineering Department
The Islamic University of Gaza, Gaza, Palestine
Tel. +970- 08- 286 0700 Ext. 2876
Mail
[email protected]
Homepage http://site.iugaza.edu.ps/mmikki/
Skype ID
mohammad.mikki
Where to find me
My Office
Building:
Room:
IT bldg
I215
Office Hours
TBA and
by appointment
Teaching Assistants
Section 101:
Eng. (TBA)
Email: (TBA)
Section 201:
Eng. (TBA)
Email: (TBA)
Course Information
Course Code:
Course Name:
Number of credits:
ECOM 3312
Data Structures and
Algorithms
(Undergraduate Course)
3
Course Description


The course covers the fundamentals of data structures and object-oriented programming.
They are two sides of the same coin:
– As a programmer becomes more proficient, they realize that how well and efficiently a
problem can be solved often depends on how the data are stored. Some of the ideas
are quite sophisticated and clever, and we'll explore a spectrum of them in this class,
ranging from fairly basic to moderately advanced structures.
– The other side is that once one realizes the importance of data structures, it is natural
to think of programs not as sequences of instructions that pass around some data, but
as data packets that come with the code needed to process them. This is at the heart
of the object-oriented design paradigm, and often leads to more modular and
extensible (and readable) programs.
 We will learn about the basics of object-oriented programming, along with many of
the interesting things that can be naturally done within the paradigm.

The class will put significant emphasis on a theoretical understanding of data structures,
their implementation, and the object-oriented viewpoint.

Assignments will contain significant programming projects along with programming-free
questions to explore how data structures work
Course Learning Outcomes
After the successful completion of the course, the student will have the:















Ability to choose appropriate and efficient data structures and algorithms to solve a problem.
Ability to compare data structures and algorithms for efficiency using algorithm analysis and
experiments.
Ability to apply algorithm analysis and knowledge of discrete mathematics to evaluate algorithms and
data structures.
Ability to implement and use linear data structures, including stacks, queues, lists
Ability to implement and use search structures and algorithms including binary search, search trees, and
hash tables.
Ability to use and implement search data structures, including search trees and hash tables.
Ability to use and implement priority queues.
Knowledge of and ability to implement sorting algorithms and compare their performance analytically
and empirically
Understanding of graphs and their representations; ability to implement graph search using BFS, DFS,
and Dijkstra's Algorithm.
Ability to solve problems using pointers and dynamically managed memory.
Ability to write recursive functions and understand when recursion is appropriate to a problem.
Ability to design, document, and implement classes and object hierarchies.
Ability to apply tools and techniques for program correctness, such as unit testing, use of a symbolic
debugger, and assert statements.
Ability to write readable and maintainable code.
Ability to explain computational solutions in person and in writing.
Prerequisites
 “Introduction to Programming”
course
 “Introduction to Computing”
course
Useful Links
 CS104 – Spring 2015: Data Structures and Object
Oriented Design, University of Southern California
bits.usc.edu/cs104
 CS 302 Data Structures, Department of Computer
Science & Engineering, UNR, Spring 2015
http://www.cse.unr.edu/~mgunes/cs302/
 CS 32: Introduction to Computer Science II,
Computer Science Department, University of
California, Los Angeles, Winter 2015
http://cs.ucla.edu/classes/winter15/cs32/
 http://www.csce.uark.edu/~jgauch/2014/slides/
Course Website
http://moodle.iugaza.edu.ps
Please check this webpage at least once a
week for:
-
lecture notes
Assignments and exams
Assignments and exams solutions
Useful links
Supplementary material, and
Announcements
Class Information
Class location, days and time
- Sec. 101: Time
Room
Sun., Tue. 12:30 -14:00
K418
- Sec. 201: Time
Room
Sun., Tue. 14:00-15:30
L401
Required Textbook and
Material
Title:
Data Structures and Algorithms
in Java,
Sixth Edition,
Authors:
Michael T. Goodrich, Roberto
Tamassia, and Michael H.
Goldwasser,
Publisher:
John Wiley & Sons, Inc., 2014
ISBN: 978-1-118-77133-4 (paperback)
The textbook is required. While
the class will not always follow
the order or presentation style of
the textbook, the textbook is an
excellent source for much of the
material.
Required Textbook and
Material
In addition to the textbook and
lecture notes, we strongly
recommend that each student
have access to a quality book on
the Java programming language
Class Expectations
 Class attendance
 Text reading in advance
 Class participation
 Working hard
Class Schedule
Week
1
Sun. 06.Sep.2015
Topic
Course Syllabus & Overview
Fundamental Data Structures
 Using Arrays
Textbook Material
Ch. 3
2
Sun.
13.Sep.2015
Fundamental Data Structures
 Using Arrays
 Singly Linked Lists
 Circularly Linked Lists .
Ch. 3
3
Sun.
20.Sep.2015
Fundamental Data Structures
 Doubly Linked Lists
 Equivalence Testing
 Cloning Data Structures
Eid El-Adha
Ch. 3
Algorithm Analysis
Ch. 4
Wed. 23.Sep.2015
4
Sun. 27.sep.2015
Class Schedule
Week
5
Sun.
04.Oct.2015
6
Sun.
11.Oct.2015
7
Sun.
18.Oct.2015
8
Sun.
25.Oct.2015
9
Sun.
01.Nov.2015
10
Sun. 08.Nov.2015
Topic
Textbook Material
Recursion
Ch. 5
Stacks
Ch. 6
Queues, and Deques
Ch. 6
List and Iterator ADTs
Ch. 7
Trees
 General Trees
 Binary Trees
Ch. 8
Trees
 Implementing Trees
 Tree Traversal Algorithms
Ch. 8
Class Schedule
Week
Topic
Textbook Material
11
Graph Algorithms
Sun. 15.Nov.2015  Data Structures for Graphs
 Graph Traversals
 Transitive Closure
Ch. 14
12
Graph Algorithms
Sun. 22.Nov.2015  Shortest Paths
 Minimum Spanning Trees
Ch. 14
13
Sun. 29.Nov.2015
Maps, Hash Tables, and Skip Lists
Ch. 10
14
Sun. 06.Dec.2015
Sorting and Selection
 Merge-Sort
 Quick-Sort
Ch. 12
15.
Review
Sun. 13.Dec.2015
First day of final exams
Sat.
26.Dec.2015
Grading Scheme
Project (s)
(TA)
Lab
(TA)
Attendance, class participation,
moodle chat and forums
10%
Midterm Exam
30%
Final exam
40%
10%
10%
Any Questions
?