CSE104 23/02/Thu

Teacher: Prof. Steven Guan Email: [email protected] Room: SD425; by appointment

Assesment

  • Final Exam (80%)
  • Assessment1 (10%) --Week 9
  • Assessment2 (10%) --Week 13

Essential TextBook Data Structures and problem solving using java

What is CSE104 About?

  • More about basics of organising, accessing, managing data and the algorithms to manipulate them

  • Touches upon foundations of designing and building programs

  • Programs with collections of Data
    • Different kinds of Data
    • Different kinds of collections
    • Data structures for implementing collections
    • Algorithms for dealing with collections
    • Programs with algorithms for access, control, i/o, etc.
    • Analysing programs, algorithms, and data structures (efficiency, correctness)

Assignment related schedule (Fri) SD546

  • 3/31 4-5pm Help session 1
  • 4/14 4-5pm Help session 2
  • 4/21 4-6pm Practical assessment 1
  • 5/5 1-5pm Help session 3
  • 5/12 4-5pm Help session 4
  • 5/19 4-6pm Practical assesment 2

L0 PDF

Data Structures

Data Collections

  • What kind of collections of data do we deal with in real life?
  • Book
  • Phone Book
  • School transcripts
  • Index cards
  • Sales data
  • Customer profile
  • Weather maps
  • Criminal records

Standard types of collections

tower of hanoi

  • Note the use of 'stack' in this game

Collections: What's the difference

  • Different types of values
  • Different structures
    • No structure - just a collection of values
    • Liner structure or values - the order matters
    • Set of key-value pairs
    • Hierarchical structures
    • Grid/table
    • ...
  • Different access disciplines
    • get, put, delete anywhere
    • get, put, delete only at the ends, or only at the top, or at both ends...
    • get, put, delete by position, or by value, or by key, or...
    • ...

Q&A

  • Name three typical type of data values in common data collections.

    integer char float real number

  • Name three typical structues seen in common data collecions.

    map queue stack

  • Name three typical operations seen in common data collections.

    get(retrive) put(insert/add) delete(remove)

  • Why do we learn data structure?

    Data procedure reduce the time/space complexity to solve specific problem

  • Can we program data structure in Java?

    yes

  • Can we program data structure in C?

    yes

Algorithms

What is an algorithm?

Algorithm vs Program

Why do we study algorithms?

Shortest path to go from A to B Dijkstra's algorithm can compute this shortest path efficiently

Our focus on algorithms

  • Algorithms that create, access, manipulate data structures ...
  • Cost and performance analysis ...
  • Performance refinement

Where are we going?

  • Using the Java Collection Library
  • Designing and Creating new Collection calsses
  • How to add, remove, search, sort, etc, efficiently
    • Fundamental data Structures
    • Fundamental algorithms
    • Measuring efficiency of algorithms

Q&A

  • Why do we insist an algorithm must terminate?

    algorithm is a design properly, prevent infinity loop

  • Why do we insist an algorithm must be precise?

    other wise its useless

  • Why instructions in an algorithm are written in a sequence?

    more advanced. cpu only read a instruction a time

L1 PDF Data structures cover ...

  • General issuse in data stucture design;
  • One-dimensional and mult-dimensional arrays;
  • Linked lists, doubly-linked lists and operations on these data structures;
  • Stacks and operations on stacks;
  • Queues and operations on queues;
  • Maps and opeartions on maps;
  • Trees & Grapsh.

Data structures

  • A data structure is a systematic way of organising a collection of data for efficient access
  • Every data structure needs a variety of algorithms for processing the data in it
  • So, it is natural to study data structures in terms of
    • properties
    • organisation
    • oerations
  • This can be done in a programming language independent way
  • Has been done in Pseudo code, Pascal, C, C++, Java, etc.

Why data structures? Aren't primitive types, like boolean, integers and strings, and simple arrays enough?

  • Yes, since the memory model of a computer is simply an array of integers
  • But, this model ..
    • is conceptually inadequate & low level, since information is usually expressed in the form of highly structured data
    • makes it difficult to describe complex algorithms, since the basic operations are too primitive

Why not just in Java? Why do we study data structures in a language independent way?

  • Java is just one of may languages within the category of object-oriented languages
  • The world's most favorite programming language changes about every five to ten years
  • However, data structure have been around since the invention of high-level programming languages THerefore.
  • We must be able to realise data structures in other languages
  • We also need the abstract context to study algorithms

We will study data structures such as

  • Arrays
  • Lists
  • Stacks
  • Queues
  • Maps
  • Trees
  • Graphs

Software quality why doing this good Software design principlies the quality of the eventual software can be measured in :

- correctness,
- efficiency.

A carefl design of the data structure used in software system helps in designing good software

Abstraction process: denotes the extracting of the essential details about an item, or a group of items, while ignoring the nonessential details. entity: denotes a model, a view, or some representation for an acutal item which leaves out some of the details of the item

Abstraction dictates that some information is more important than other information, but does not provide a specific mechanism for handling the unimportant information.

data abstraction: identify which details of how data is stored and can be manipulated are important and which are not procedural abstraction: identify which details of how a task is accomplished are important and which are not

Key of abstraction...

  • Extracting the commonality of components and hiding their details
  • Abstraction typically focuses on the outside view of an object/concept

Communication based on Huffman coding

Huffman coding - Abstraction example

  • Huffman coding is an effective way of encoding (and decoding) textual (or non-textual) data. It has been used in communication, e.g. source coding
  • A large information system may need a piece of software that carries out the Huffman encoding of the data stored on a disk or generated from some data source.
  • The Huffman encoding software uses priority queue to accomplish its tasks.
  • important points:
    • The description abstracts from all details on how the priority queue and its operations are implemented.
    • Nonetheless the description enables a programmer to focus on the design of the particular module using the priority queue functions given.

Huffman coding – Key ideas

  • Based on the frequency of occurrence of a data item (pixelin images, alphabet in texts)
  • The principle is to use a smaller number of bits to encode the data that occurs more frequently
  • Codes are stored in a Code Book which may be constructed for each image (alphabet) or a set of images
  • In all cases the cases the code book plus encoded data must be transmitted to enable decoding

Huffman coding - core book(core table)

Huffman coding-en-/ed-coding tree

Q&A

  • Given the following codebook, design the corresponding Huffman coding scheme for it**

  • Using the codebook developed, decode:

    • 10011
    • 01101011
    • 0010001

Use of abstraction in the design of Huffman coding

  • Components
    • Encoding
      • Algorithms?
      • Data structures?
    • Decoding
      • Algorithms?
      • Data structures?
    • Codebook management
      • Algorithms?
      • Data structures?

Detecting commonality in Huffman coding - en-/decoding tree construction Data structure used: List A(15), B(7), C(6), D(6), E(5)>> List A(15),B(7),C(6),P1(11)>> List A(15),P1(11),P2(13)>> List A(15),P3(24)>> List P4(39)>>

Priority queue Operations: EXTRACT-MIN, INSERT

Use of abstraction in Huffman encoding – data structure & algorithm

  • A priority queue is a data structure for maintaining a set Q of elements each with an associated value (and key). not finish
  • A priority queue supports the following operations:
    • INSERT(Q,x) inserts the element x into Q.
    • MIN(Q) returns the element of Q with minimal key.
    • EXTRACT-MIN(Q) removes and returns the element of Q with minimal key.
  • Question: difference btn MIN & EXTRACT-MIN
  • A binary tree is a data structure for maintaining a set Q of nodes each with an associated value and options of left and right child nodes.
  • A binary tree supports the following operations:
    • ALLOCATE-NODE creates a new node, returning a reference to the node z created.
    • right(z) refers to the right child node of z
    • left(z) refers to the left child node of z.

results matching ""

    No results matching ""