Transcript Document

Course ‘Data structures
and algorithms – using
Java’
Teaching materials and presentation
experience
Anastas Misev
Institute of Informatics
Faculty of Natural Science and Mathematics
University Ss Cyril and Methodius
Skopje, Macedonia
[email protected]
Agenda









The course
Syllabus
Bibliography
Evaluation
Grading
Teaching materials
Assignments
Projects
Students feedback
The course







Basic course in data structures and algorithms
4th semester
Course delivered via moodle at
http://courses.ii.edu.mk
Preceded by a course in programming languages
(where Java is introduced) in the 3rd and two more
introductory programming courses (1st and 2nd
semester)
2 hours of lectures + 1 hour tutorial + 2 hours labs
Lectures and tutorial combined
English slides with Macedonian presentation
Supporting site (moodle)
Syllabus
Lectures (2x45min)
Tutorial (1x45min)
Topic
Reference
Topic
Reference
Algorithm analysis - Model of
computer
Preiss, ch.2
Java review
Asymptotic notation
Preiss, ch.3
Asymptotic analysis of
algorithms (measuring)
Preiss, ch.3
Foundational data structures
Watt-Brown ch.3, 4
Java implementations of found.
data struct.
Watt-Brown ch.3, 4
Abstract Data Types
Watt-Brown, ch.5
ADT in Java class library
Preiss, ch.5
Stacks and queues
Watt-Brown, ch.6,7
Application of stacks and
queues
Preiss, ch.6
Lists
Watt-Brown, ch.8
Design patterns and
applications of lists
Preiss, ch.7
Syllabus (cont.)
Lectures (2x45min)
Tutorial (1x45min)
Topic
Reference
Topic
Reference
Hash tables
Watt-Brown ch.9
Sample Java implementation
Watt-Brown ch.9
Trees
Preiss, ch.9
Watt-Brown, ch.14
Tree Java implementation
Preiss, ch.9
Priority queues and heaps
Preiss, ch.11
Watt-Brown, ch.13
Applications
Preiss, ch.11
Sorting
Sedgewick, part III
Preiss, ch.14
Java implementation
Preiss, ch.14
Search threes
Watt-Brown, ch.16
Preiss, ch.10
Applications
Preiss, ch.10
Graphs
Brown-Watt, ch.15
Preiss, ch.16
Representation and
algorithms
Brown-Watt, ch.15
Preiss, ch.16
Algorithmic patterns
(Brut-force, backtracking, topdown, bottom-up)
Preiss, ch.14
Example algorithms and Java
implementations
Preiss, ch.14
Bibliography


Preiss: Bruno Preiss, Data Structures and
Algorithms with Object-Oriented Design Patterns in
Java, John Wiley & Sons, also available on line at
http://www.brpreiss.com/books/opus5/ (with email
permission to use all resources)
Watt-Brown: David Watt and Deryck F. Brown, Java
Collections, An Introduction to Abstract Data Types,
Data Structures and Algorithms, John Wiley & Sons
(Material permitted to be used with notices,
http://www.dcs.gla.ac.uk/~daw/books/JC/index.html)
Evaluation

Weekly assignments



Projects







More complicated programming and/or essay assignments
Colloquia (recommended)


Performed during the labs and uploaded
Programming or essay
Consist of practical and theoretical part
Each part is passed with minimum 50%
Passes both practical parts – no practical (written) exam
Passed both theoretical parts – no theoretical (oral) exam
Practical exam
Oral exam
Activity during the course

Using the moodle system, for each lecture and tutorial, a topic to discus its
quality will be posted. The students with the most constructive and critical
comments will be awarded up to 20 extra points
Points
Element
Weekly assignments
Qty
Points
Total
10
5
50
Projects
2
25
50
Colloquia (practical)
2
50
100
Colloquia (theory)
2
50
100
(extra)
20
20
Activity during the course
320
Total
Element
Weekly assignments
Qty
Points
Total
10
5
50
Projects
2
25
50
Practical Exam
1
100
100
Oral (theory) Exam
1
100
100
(extra)
20
20
Activity during the course
Total
320
About the grading





Weekly assignments are mandatory
 Dye date will be announced with each assignment
 No late submissions
Projects are mandatory
 Dye date will be announced with each assignment
 No late submissions (or lower grading based on the time
passed the dye date)
The course can be passed either through colloquia or written
and oral exam.
Activity during the course is optional, but recommended for
the students aiming for higher grades
The grading will be performed according to the following table
Grading scheme
Points
Grade
291-320
10
256-290
9
221-255
186-220
151-185
8
7
6
Teaching materials

Power Point presentations





Given in English
Most of the students did not mind
Some commented about the language
Books listed
Some additional material in Macedonian,
regarding dynamic programming
Assignments

10 weekly assignments




Supposed to be done during the labs
Usually complement the labs
Most of them were programming tasks involving a
variation of the tasks done at the labs
Submission rate was relatively high
Assignments (cont)
Projects



More advanced assignments
Require individual work
Project 1




Common to all students
Tree of arithmetical expressions
Demonstrates the knowledge of several important
data structures (from file to tree, then to postfix
and finally evaluation)
Deliverables include programming code, sample
input and output files and essay in .doc.
Projects (cont.)

Project 2




Individual projects
Student were asked to choose category of problem that
they would like to do
4 categories
 Programming problems (max 30 points)
 Visualization applets (max 30 points)
 Additional programming examples of data structures (max
20 points)
 Enhancement of the teaching materials (max 15 points)
Most often the first and the last were selected
Students’ feedback




The first time this course was delivered using
this method
Also, the first course delivered by the
teacher
Students’ feedback was more than welcome
For each topic presented, a discussion topic
was posted in a special forum for the quality
of the teaching and the materials
Students’ feedback (cont.)





Almost all topics had some discussion attached
Most of the comments were proposing integration of
more examples into the slides
Some were concerning errors in the examples with
programming code
Only last couple of topics were with no comments (I
suppose the enthusiasm degrades toward the end
of the semester)
All the comments were carefully read by the
teaching stuff and when necessary a response was
posted promptly
Future work






The course was given to the last generation using the previous
curriculum
In the new one, the Programming languages course is omitted
This means that the introduction to Java will be done in this
course
Fortunately, the number of hours per week increased to 3 + 2 + 2
(giving 1 more lecture and 1 more tutorial hour)
The course is changed with the addition of 7 new topics
regarding Java fundamentals, that will be covered in the firs 3-4
weeks
On the next year’s workshop will share the new experiences 
Questions and comments