Recep Tayyip Erdogan University

Download

• PDF
• DOCX
• SLIDE

Download Legacy

• WORD
• PDF

*TBD: To Be Defined.

A. Course Description

This course covers the fundamentals of data structure and file organization. The course scope explains using digital data mapping in programming to use data in application run-time memory or long-term file storage. The course discusses various implementations of these data objects and programming styles, and run-time representations. The study also looks at sorting, searching, and graph algorithms. This course aims to provide digital data structures for real-world problems, as well as how data is shaped and mapped to memory or storage solutions. The class will be based on sharing expertise and guiding students to discover learning methods and practice for data structure topics. By making programming applications and projects in the courses, the learning process will be strengthened by practicing rather than theory.

B. Course Learning Outcomes

After completing this course satisfactorily, a student will be able
to:

• Describe how common linear and non-linear data structures such as arrays, matrices, linked structures, queues, stacks, trees and graphs are represented in run time and storage memory and used by algorithms.

• Compare and contrast the benefits of dynamic and static data structures implementations.

• Understand basic industrial data structure definitions such as ASN.1 / BER TLV / PER TLV.

• Describe how run-time application data stored in a file and organized.

• Interpret a problem and define data structures for solution by using a C/C++, Java or C# application solve that problem in data structure manner.

• Compare alternative implementations of data structures with respect to performance and analysis space and time complexity.

• Understand data structure based sorting and searching algorithms.

• Describe hashing and indexing methods for file organization and processing.

• Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing in memory and file storage.

• Combine programming skills with data structures know-how and generate efficient solutions for real-life problems.

C. Course Topics

• Data-in-use, Data-in-transit and Data-at-rest concepts.

• Data Structures Space and Time Complexity Analysis

• Data and Variable Mappings

• ASN.1 / BER TLV / PER TLV

• Linked Lists (Single, Circular, Double, XOR)

• Skip List

• Strand Sort

• Arrays (Rotations, Arrangement, Rearrangement, Searching and Sorting)

• Matrices and Spare Matrices

• Stacks (Array and Linked List) and FILO (First in Last Out)

• Expressions (Infix, Postfix and Prefix) and Infix to Postfix Conversions and Postfix Evaluation

• Queues (Standard, Circular and Double Ended) (Array and Linked List) (FIFO-First-in First-Out or FCFS-Fist Come First Serve)

• Multievel Queues (MLQ)

• Hanoi Tower

• Tree Structures and Binary Tree and Traversals (In-Order, Pre-Order, Post-Order)

• Heaps (Max, Min, Binary , Binomial, Fibonacci, Leftist, K-ary) and Priority Queue

• Heap Sort

• Huffman Coding

• Graph Representations (Adjency Matrix, Incidence Matrix, Adjency List) and Basics

• Graph Traversals ( Depth-First Search (DFS), Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS), Breadth-First Search (BFS), Depth-limited Search, Uniform Cost Search, Bidirectional Search)

• Water Jug Problem

• Graph Topological Sorting

• Graph Minimum Spanning Tree (MST)

• Graph Backtracking ( Tug of War, n-Queen’s, m Coloring, Euler& Hamiltonian Path)

• Graph Shortest Paths

• Graph Connectivity, Max Flow, Isomorphism, Canonization and Cuts (Max /Min)

• Alpha-Beta Prunning

• Hasse Diagrams

• Petri Nets

• Bipartite Graphs

• Graph Cycle Detection (Brent’s, Hare and Tortoise Algorithms)

• Bayesian Network

• Linear, Binary, Interpolation and Fibonacci Search

• Hashing and Hash Tables (Direct-Adress Tables, Hash Tables, Hash Functions, Open Adressing, Perfect Hashing)

• Common Sorting Algorithms ( Insertion, Selection, Radix, Quick, Heap, Permutation, Gnome, Comb, Flash, Stooge, Bees, Lucky, Indirect (Pointer), External ( Segmented), Shaker/Bidirectional Bubble, Shell Sort)

• Comparison of Sorting Methods

• Common Tree Data Structures and Operations ( Binary Search Tree, AVL Tree, B Tree and Derivations (2 3 4 Trees, 2 3 Trees, B+ Trees, B# Trees), R Tree, Red-Black Tree, Splay Tree, Van Emde Boas Tree, Binomial Tree, Minimax Tree)

• Comparison of Search Trees

• Augmenting Data Structures

• String LCS Problem (Hunt Macllory, Levenstein, Wagner-Fischer)

• String Alignment (Needleman Wunsch, Smith Waterman, Hunt Macllory), Tokenizer and Comparison

• String Search (Reverse Factor) Algorithms (Knuth-Morris-Pratt, Horspool, Boyer Moore, Brute-Force, DFA Text Search)

• Tries and Patricia Tree (Radix Tree)

• Data Structure for Disjoint Sets

• Sequential File Organization (Binary Search, Interpolation Search, Self-Organizing Sequential Search)

• Direct File Organization Locating Information

• Direct File Organization Hashing Functions ( MD5, HAVAL, SHA1, Key Mod N, Key Mod P, Truncation, Folding, Squaring, Radix Conversion, Polynomial Hashing, Alphabetic Keys, Collisions)

• Direct File Organization Collision Resolution

• Direct File Organization Coalesced Hashing (EISCH, LISCH, BEISCH, BLISCH, REISCH, RLISCH, EICH, LICH)

• Direct File Organization Progressive Overflow (Linear Probing, Quadratic Probing)

• Direct File Organization Double Hashing, Use of Buckets, Linear Quotient, Brent’s Method, Binary Tree and Computed Chaining Insertion (CCI)

• Perfect Hashing and SimHash for Direct File Organization

• Comparison of Collision Resolution Methods

• Indexed Sequential File Organization

• Secondary Key Retrivals and Bits and Hashing for Classification and Checking

• Binary Tree Structures for Files (Binary Search, AVL Trees, Internal Path Reduction Trees)

• B-Trees and Derivates for Files (B Tree, B+Tree, B# Tree)

• Hashing Techniques for Expandable Files (Extendible, Dynamic and Linear Hashing)

• Tries, Approximate String Matching, Trie Hashing, Patricia Tree and Digital Search Tree for File Organization

• Secondary Key Retrivial (K-d Trees and Grid Files)

• File Sorting (Insertion, Quick, Heap Sorts, External Sorting, Sorting By Merging and Disk Sort)

D. Textbooks and Required Hardware or Equipment

This course does not require a coursebook.
If necessary, you can use the following books and open-source online resources.

• C How to Program, 7/E. Deitel & Deitel. 2013, Prentice-Hall.

• Intro to Java Programming, Comprehensive Version (10th Edition) 10th
  Edition by Y. Daniel Liang

• Introduction to Algorithms, Third Edition By Thomas H. Cormen,
  Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

• Problem Solving and Program Design in C, J.R. Hanly, and E.B.
  Koffman, 6th Edition.

• Alan L. Tharp. 1988. File organization and processing. John Wiley
  & Sons, Inc., USA.

• Richard Jankowski. 2010. Advanced data structures by Peter Brass
  Cambridge University Press 2008. SIGACT News 41, 1 (March 2010), 19–20.
  DOI:https://doi.org/10.1145/1753171.1753176

• Robert Sedgewick and Kevin Wayne. 2011. Algorithms (4th. ed.).
  Addison-Wesley Professional.

• Additional Books TBD

During this course, you should have a laptop for programming practices. You will have your development environment, and you will use this for examination and assignments also classroom practices.

E. Grading

You will complete one project and two written quizzes throughout the semester. You are expected to submit your Midterm Project Report at the midterm, demonstrating progress and outputs aligned with your project plan. In the 15th week, you will present and submit your Final Project Report. You will take a written quiz in the 8th week and another in the 14th week.

$$Grade_{Midterm} = 0.6 RAP1 + 0.4 QUIZ1$$

$$Grade_{Final} = 0.7 RAP2 + 0.3 QUIZ2$$

$$Passing Grade = (40 * Grade_{Midterm} + 60 * Grade_{Final}) / 100$$

F. Instructional Strategies and Methods

The basic teaching method of this course will be planned to be face-to-face in the classroom, and support resources, homeworks, and announcements will be shared over google classroom. Students are expected to be in the university. This responsibility is very important to complete this course with success. If pandemic situation changes and distance education is required during this course, this course will be done using synchronous and asynchronous distance education methods. In this scenario, students are expected to be in the online platform, zoom, or meet at the time specified in the course schedule. Attendance will be taken.

G. Late Homework

Throughout the semester, assignments must be submitted as specified by the announced deadline. Overdue assignments will not be accepted.

Unexpected situations must be reported to the instructor for late homeworks by students.

H. Course Platform and Communication

Google Classroom will be used as a course learning management system. All electronic resources and announcements about the course will be shared on this platform. It is very important to check the course page daily, access the necessary resources and announcements, and communicate with the instructor as you needed to complete the course with success

I. Academic Integrity, Plagiarism & Cheating

Academic Integrity is one of the most important principles of RTEÜ University. Anyone
who breaches the principles of academic honesty is severely punished.

It is natural to interact with classmates and others to "study together". It may also be the case where a student asks to help from someone else, paid or unpaid, better understand a difficult topic or a whole course. However, what is the borderline between "studying together" or "taking private lessons" and "academic dishonesty"? When is it plagiarism, when is it cheating?

It is obvious that looking at another student's paper or any source other than what is allowed during the exam is cheating and will be punished. However, it is known that
many students come to university with very little experience concerning what is acceptable and what counts as "copying", especially for assignments.

The following are attempted as guidelines for the Faculty of Engineering and Architecture students to highlight the philosophy of academic honesty for assignments for which the student will be graded. Should a situation arise which is not described below, the student is advised to ask the instructor or assistant of the course whether what they intend to do would remain within the framework of academic honesty or not.

a. What is acceptable when preparing an assignment?

• Communicating with classmates about the assignment to understand it better

• Putting ideas, quotes, paragraphs, small pieces of code (snippets) that you find online
  or elsewhere into your assignment, provided that

  • these are not themselves the whole solution to the assignment,

  • you cite the origins of these

• Asking sources for help in guiding you for the English language content of your
  assignment.

• Sharing small pieces of your assignment in the classroom to create a class discussion
  on some controversial topics.

• Turning to the web or elsewhere for instructions, references, and solutions to
  technical difficulties, but not for direct answers to the assignment

• Discuss solutions to assignments with others using diagrams or summarized statements but not actual text or code.

• Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your assignment for you.

b. What is not acceptable?

• Ask a classmate to see their solution to a problem before submitting your own.

• Failing to cite the origins of any text (or code for programming courses) that you discover outside of the course's lessons and integrate into your work

• Giving or showing a classmate your solution to a problem when the classmate is struggling to solve it.

J. Expectations

You are expected to attend classes on time by completing weekly course requirements (readings and assignments) during the semester. The main communication channel between the instructor and the students will be emailed. Please send your questions to the instructor's email address about the course via the email address provided to you by the university. Ensure that you include the course name in the subject field of your message and your name in the text field. In addition, the instructor will contact you via email if necessary. For this reason, it is very important to check your email address every day for healthy communication.

K. Lecture Content and Syllabus Updates

If deemed necessary, changes in the lecture content or course schedule can be made. If any changes are made in the scope of this document, the instructor will inform you about this.

Course Schedule Overview

$$End-Of-Syllabus$$