CMP507 Data Structure and Algorithm in C Note #1 Dr. Peter Wang 1. The most important thing as a student of computer science is to learn the skills to solve problems. 2. Software : Aplication Domain Knowledge + Program. 3. Program : Data Structure (object) + Algoritm (operation). 4. Data Structure: To allocate memory for objects such that it facilitate the algorithm design for the application. 5. Top-Down design: To decompose a complex problem into several subproblems repeatly until all the subproblems have a simple solution. 6. Computer Science: a. Science b.Engineer c.Mathematics and Logic d. Communication e.Interdisciplinary 7. Three sections of a program: a. Program header b. Declaration section c. Executable section 8. Three structures of structure programming: a. Sequential b. Selection c. Looping 9. Six categories of instruction set: 1. Input/outout 2. Data Movement (Assignment) 3. Arithmetic 4. Logical 5. Selection 6. Iteration 10. Syntax: The grammar rules of a specific language. 11. Semantics: The meaning of an instruction/statement. 12. Declaration: Allocate memory space for objects by using appropriate data structures. 13. Executable statement: Statement to implement the algorithm to solve the specific problem. 14. Syntax Diagram: The diagram to define the syntax of a prgramming language. 15. OOP: Object + operation. (Two major ingredians are Top-Down design & Modualrity) The components of object-oriented programs are: Object: The object in OOP includes the basic data or data structure and the related procedures and functions required to keep the object complete. To make the object like an abstracted data type. Method: A method is a procedure or function that becomes part of the object. It provides the abstraction to the object's data. Encapsulation: The combining of data structures and methods is called encapsulation. If encapsulation is performed correctly, the user of the object should never need to access the data of object directly. 16. Data Representation: a. Character: Alphabets, numbers, and symbols use a combination of 8 bits (one byte) to represent a character in a coding system. The sequence of each character (an integer value from 0 to 255 in that order) from lowest to highest in a coding system is called Collating Sequence. b. Integer: an integer value can be represented by: 1. Unsigned 2. Sign-Magnitude 3. One's Complement 4. Two's Complement 5. Excess (2 ** (N-1)) c. Floating Point: Sign(+,-) Exponent(base 2, 8, 10, 16 and bias 2**(n-1)-1 ) Mantissa( with or without hidden bit) IEEE standard single precision (1,8,23 , base 2, bias 127, with hidden bit) IEEE standard double precision (1,11,52, base2, bias 1023, with hidden bit) 17. Abstract Data Type (ADT): ADT is a way of packaging some intermediate-level data structures and their operations into a useful collection whose properties have been carefully studied and with clean and simple interface. The ADT define "WHAT" and not "HOW" to implement. 18. Efficiency is the major concern of data structure and algorithm. Time/space/money tradeoff is the decision to make. 19. The process of writing programs to create computer applications involves the "representation" of objects, operations, and behaviors required in the application in term of the primitives available in the computational medium. 20. It is often cheaper to use libraries of reusable software components than it is to start from scratch by using programming language to "roll your own". 21. The human mind has limits to its capacity to deal with intellectual complexity. 5..9 chunks of data. - Packaging representation entities into modules and layers. - Information hiding is the act of concealing the internal details from view and present clean, simple interface. - Abstraction is to extract a few simple details to put into interface for user to employ. - The intermediate-level data structure have a high utility in solving programming problems. 22. Context Free Grammar (CFG), Backus-Naur Form (BNF): - A method to describe the specifications for the syntax of a programming language. - A CFG is denoted by G = (V,T,P,S), where V and T are finte sets of variables (non-terminals), and terminals. Assume that V and T are disjoint. P is finite set of productions; each production is of the form A -- > a, where A is a varibale, and a is a string of symbols from (V U T)*. Finally, S is special variable called the Start Symbol. 23. Goal of Data Structure and Algorithm (DSA): - To present various kinds of ADTs - To develop their properties - To develop their use - To enrich your knowledge of ideas and concepts useful for crafting practical representations and software systems. - To analyze the DSA and its time/space tradeoff. 24. Intermediate-level DS: Files, Lists, Trees, Arrays, Records, Strings, Tables, Stacks, Queues, Sets, and Graphs. 25. Algorithm: A step by step procedure to solve a problem. - A finite set of steps - Definite: Clear what should be done - Effective: Basic enough to be carried out by pen and paper - Input/Output - Terminate after a finite number of operations 26. Software Development Life Cycle: - Request for Proposal (RFP) - Proposal - Requirements Analysis - Feaiblity Study - System Analysis - System Design - Program design - HIPO/flowchart - Coding - Testing/Debugging - Documentation - Maintenance and Enhancement - Data flow and test cases - Graphics User Interface (GUI). 27. User view of a computer: Instruction set, Register set, and Addressing modes. 28. Four aspects of a variable: Name, Value, Address/location/pointer, Other attributes 29. Linked data representations are especially useful for applications in which it is difficult to predict the size and shape of the data structures needed. The Linked representation can grow and shrink piece-by-piece. A pointer is just the memory address of a block of storage. 30. Byte: The basic unit of memory address in byte machine. 31. MIPS: Million Instructions Per Second. 32. TFIPS: Trillion Floating Instructions Per Second. 33. Instruction Cycle: - Instruction Time: Fetch instruction from memory into instruction register - Execution Time: Decode, Execute, and Restore into memory 34. Bus: The electrical path for signals to flow. A set of wires. 35. File access methods: Sequential, Direct, and Indexed. 36. Alias: Two pointers point to the same memory location 37. Dereferencing: When we follow a pointer to the unit of storage for which the pointer value is the address, we dereference the pointer. i.e. indirect addressing. 38. Recursion is an important concept in computer science. It can sometimes be used to formulate unusually simple and elegant solutions to problems that are hard to solve otherwise. Recursion is the best choice for those applications which are recursive nature. 39. Once a person has understood the way in which variables are used in programming, he has understood the quintessence of programming. 40. A functional programming language is one which achieves its effects by applying functions, either recursively or through composition, and for which all of its expressions obey the principle of referential transparency.