DOC PREVIEW
UNL CSCE 235 - Introduction to Discrete Structures

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction CSCE 235 Introduction to Discrete StructuresOutlineIntroductionTopicsWhy Discrete Mathematics? (I)Why Discrete Mathematics? (II)Problem Solving requires mathematical rigorScenario IScenario IIScenario IIIWhat’s your job?The goal of this courseBasic PreliminariesIntroduction CSCE 235 Introduction to Discrete StructuresFall 2008Instructor: Berthe Y. Choueiry (Shu-we-ri)GTA: Jie Fenghttp://cse.unl.edu/~choueiry/F08-235/http://cse.unl.edu/~cse235/IntroductionCSCE 235, Fall 20082Outline•Introduction: syllabus, schedule, web, topics•Why Discrete Mathematics?•Basic preliminariesIntroductionCSCE 235, Fall 20083Introduction•Roll•Syllabus•Lectures: M/W/F 12:30—1:20 pm (Avery 109)•Recitations: Tue 5:30—6:20 pm (Avery 108)•Office hours:–Instructor: M/W 1:30—2:30 pm (Avery 123B)–TA: M/Thu 10:00—11:00 am (Student Res. Center)•Must have a cse account•Must use cse handin•Bonus points: report bugs•Web pageIntroductionCSCE 235, Fall 20084TopicsTopic SectionsPropositional Logic 1.1—1.2Predicate Logic 1.3—1.4Proofs 1.5—1.6Sets 21.—22Functions 2.3Relations 8.1,8.3—8.6Algorithms 3.1—3.3Induction 4.1—4.2Counting 5.1—5.2Combinatorics 5.3—5.5Recursion 7.1—7.2PIE 7.5Graphs 9.1—9.5Trees 10.1—10.3IntroductionCSCE 235, Fall 20085Why Discrete Mathematics? (I)•Computers use discrete structures to represent and manipulate data.•CSE 235 and CSE 310 are the basic building block for becoming a Computer Scientist•Computer Science is not Programming•Computer Science is not Software Engineering•Edsger Dijkstra: “Computer Science is no more about computers than Astronomy is about telescopes.”•Computer Science is about problem solving.IntroductionCSCE 235, Fall 20086Why Discrete Mathematics? (II)•Mathematics is at the heart of problem solving•Defining a problem requires mathematical rigor•Use and analysis of models, data structures, algorithms requires a solid foundation of mathematics•To justify why a particular way of solving a problem is correct or efficient (i.e., better than another way) requires analysis with a well-defined mathematical model.IntroductionCSCE 235, Fall 20087Problem Solving requires mathematical rigor•Your boss is not going to ask you to solve an MST (Minimal Spanning Tree) or a TSP (Travelling Salesperson Problem)•Rarely will you encounter a problem in an abstract setting.•However, he/she may ask you to build a rotation of the company’s delivery trucks to minimize fuel usage•It is up to you to determine –a proper model for representing the problem and –a correct or efficient algorithm for solving it.IntroductionCSCE 235, Fall 20088Scenario I•A limo company has hired you/your company to write a computer program to automate the following tasks for a large event•Task1: In the first scenario, businesses request–limos and drivers –for a fixed period of time, specifying a start data/time and end date/time and –a flat charge rate.•The program must generate a schedule that accommodates the maximum number of customersIntroductionCSCE 235, Fall 20089Scenario II•Task 2: In the second scenario, the limo service allows customers to bid on a ride to that the highest bidder get a limo when there aren’t enough limos available.•The program should thus make a schedule that–Is feasible (no limo is assigned to two or more customers at the same time)–While maximizing the total profitIntroductionCSCE 235, Fall 200810Scenario III•Task 3: Here each customer is allowed to specify a set of various times and bid an amount for the entire event. The limo service must choose to accept the entire set of times or reject it.•The program must again maximize the profit.IntroductionCSCE 235, Fall 200811What’s your job?•Build a mathematical model for each scenario •Develop an algorithm for solving each task.•Justify that your solutions work–Prove that your algorithms terminate. Termination–Prove that your algorithms find a solution when there is one. Completeness–Prove that the solution of your algorithms is correctSoundness–Prove that your algorithms find the best solution (i.e., maximize profit). Optimality (of the solution)–Prove that your algorithms finish before the end of life on earth. Efficiency, time and space complexityIntroductionCSCE 235, Fall 200812The goal of this course•The goal of this course is to give you the foundations that you will use to eventually solve these problems.–Task1 is easily (i.e., efficiently) solved by a greedy algorithm–Task2 can also be (almost) easily solved, but requires a more involved technique, dynamic programming–Task3 is not efficiently solvable (it is NP-hard) by any known technique. It is believed today that to guarantee an optimal solution, one needs to look at all (exponentially many) possibilities.IntroductionCSCE 235, Fall 200813Basic Preliminaries•A set is a collection of objects. •For example:–S = {s1,s2,s3,…,sn} is a finite set of n elements –S = {s1,s2,s3,…} is a infinite set of elements.•s1  S denotes that the object s1 is an element of the set S•s1  S denotes that the object s1 is not an element of the set S•LaTex–$S=\{s_1,s_2,s_3, \ldots,s_n\}$–$s_i \in S$–$si \notin


View Full Document

UNL CSCE 235 - Introduction to Discrete Structures

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Introduction to Discrete Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Discrete Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Discrete Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?