Data Structures
데이터 구조
2024년 2학기 • 전북대학교
Schedule 강의일정
| Date | Lecture | Content | Logistics | |
|---|---|---|---|---|
| 9/2 |  | Week #1: Introduction Chapter 1: Information in Memory
| ||
| 9/9 |  | Week #2: Chapter 2: Binary Search Chapter 3: Dynamic Data Structures
| [ 과제 ] GitHub File Repository | |
| 9/16 | No Class Chuseok | |||
| 9/23 |  | Week #4: Chapter 4: Stacks and Queues
| ||
| 9/30 |  | Week #5: Chapter 4: Breadth-First Search, Depth-First Search
| ||
| 10/7 |  | Week #6: Chapter 5: Binary Search Trees No Class Hangul Day
| ||
| 10/14 |  | Week #7: Linked List coding Midterm Study Guide
| ||
| 10/21 | Midterm Test | |||
| 10/28 |  | Week #9: Chapter 6: Tries and Adapting Data Structures Chapter 7: Priority Queues and Heaps
| ||
| 11/4 |  | Week #10: Chapter 8: Grids Chapter 9: Spatial Trees
| ||
| 11/11 |  | Week #11: Chapter 10: Hash Tables
| ||
| 11/18 |  | Week #12: Chapter 11: Caches
| [ 과제 ] Coding with Stacks & Queues | |
| 11/25 |  | Week #13: Chapter 12: B-Trees
| ||
| 12/2 |  | Week #14: Chapter 13: Bloom Filters
| ||
| 12/9 |  | Week #15: Chapter 14: Skip Lists Chapter 15: Graphs Conclusion
| ||
| 12/16 | Final Test Study Guide | |||
Assignments 과제
Assignment Files:
-
0-python-basics.ipynb(4 pts)- Basic Data Types (int, float, complex, arrays, objects)
- Getting User Input
- Conditionals
- Loops (for, while)
-
1-info-in-memory.ipynb(6 pts)- Array value swap
- Insertion sort
- String equality
-
2-binary-search-linked-lists.ipynb(10 pts)- Linear scan
- Binary search
- Array doubling
- Linked lists
- Lookup
- Insertion
- Deletion
Overview 개요
Data Structures the Fun Way No Starch Link
This accessible and entertaining book provides an in-depth introduction to computational thinking through the lens of data structures — a critical component in any programming endeavor. Through diagrams, pseudocode, and humorous analogies, you’ll learn how the structure of data drives algorithmic operations, gaining insight into not just how to build data structures, but precisely how and when to use them.
This book will give you a strong background in implementing and working with more than 15 key data structures, from stacks, queues, and caches to bloom filters, skip lists, and graphs. Master linked lists by standing in line at a cafe, hash tables by cataloging the history of the summer Olympics, and Quadtrees by neatly organizing your kitchen cabinets. Along with basic computer science concepts like recursion and iteration, you’ll learn:
- The complexity and power of pointers
- The branching logic of tree-based data structures
- How different data structures insert and delete data in memory
- Why mathematical mappings and randomization are useful
- How to make tradeoffs between speed, flexibility, and memory usage
Data Structures the Fun Way shows how to efficiently apply these ideas to real-world problems—a surprising number of which focus on procuring a decent cup of coffee. At any level, fully understanding data structures will teach you core skills that apply across multiple programming languages, taking your career to the next level.
Textbook 교재
 |
|
|---|
Logistics 수업운영
Course Information / 과정정보
시간이 지나도 변하지 않고 컴퓨팅 세계의 기반을 강화하는 데 도움이 되는 전문적이고 안전하며 이식 가능한 C 코드를 작성하는 방법을 알아본다.
- 프로그래밍(50%) 직무에 필요한 문제 또는 시스템을 프로그래밍 언어로 구현할 수 있는 역량
- 전공기초(40%) 정보통신전공을 수행할 수 있는 공학적 기초개념, 수학, 물리학 등의 기본역량
- 자기주도문제해결(10%) 프로젝트, 캡스톤디자인 및 지식재산권, 공학경영, 논문작성 등 전공분야에 밀접하게 연관된 비전공분야의 역량
Students will learn how to write professional, safe, and portable C code that doesn’t change over time and helps strengthen the foundations of the world of computing.
- Programming (50%) Ability to implement problems or systems required for the job in a programming language
- Major foundations (40%) Basic competencies such as basic engineering concepts, mathematics, physics, etc.
- Self-directed problem solving (10%) Competence in non-major fields closely related to major fields, such as project, capstone design and intellectual property rights, engineering management, and thesis writing
Policies 규정
Grading 평가방법
Most of my courses are graded based on the following components. Please note that the weights of each component may vary depending on the course. The grading policy will be announced in the first class and will be available on the course website.
대부분의 강의는 다음 구성요소에 따라 평가됩니다. 각 구성요소의 가중치는 강의에 따라 다를 수 있습니다. 평가 방법은 첫 강의에서 발표되며 강의 웹사이트에서 확인할 수 있습니다.
- Attendance (& Participation) 출석 (& 참여도)
- Assignments & Practice Exercises 과제 (연습문제) 및 실습 (수업 활동 결과)
- Project (or Research Paper & Presentation) 프로젝트 (또는 논문과 발표)
- Tests (Midterm & Final) 중간고사와 기말고사
Attendance (& Participation) 출석 (& 참여도)
This may be the most important part of the class. Please pay careful attention to the following.
이것은 수업의 가장 중요한 부분일 수 있습니다. 다음 사항에 주의 깊게 주목해 주세요.
I appreciate everyone being actively involved in the class! Students who will succeed are those who are actively involved.
저는 수업에 적극적으로 참여해 주시는 모든 분들을 감사하게 생각합니다! 성공할 학생들은 적극적으로 참여하는 학생들입니다.
- Attendance:
- You are expected to attend all classes. If you miss a class, you are responsible for getting the notes from a classmate or completing the assignments you miss.
수업에는 모두 참석해야 합니다. 수업을 빠지는 경우, 수업 내용을 동료로부터 받거나 빠진 과제를 완료하는 것은 _당신_의 책임입니다. - Generally, if you miss more than 15% of the classes (7 hours in a 45-hour course, 9 hours in a 60-hour course), you will get a lower grade.
일반적으로, 수업의 15% 이상을 빠지는 경우 (45시간 강의에서 7시간, 60시간 강의에서 9시간), 낮은 성적을 받게 됩니다. - If you miss more than 25% of the classes (11 hours in a 45-hour course, 15 hours in a 60-hour course), you will fail the course.
수업의 25% 이상을 빠지는 경우 (45시간 강의에서 11시간, 60시간 강의에서 15시간), 과락이 됩니다.
- You are expected to attend all classes. If you miss a class, you are responsible for getting the notes from a classmate or completing the assignments you miss.
- Participation:
- Active participation is expected in all classes. This means that you are engaged in the class, asking questions, answering questions, and participating in discussions.
모든 수업에서 적극적인 참여가 기대됩니다. 이는 수업에 집중하고 질문을 하며 질문에 답하고 토론에 참여하는 것을 의미합니다. - Disinterest: Students who are not interested in the class do not study, do not participate, and do not do well on the tests. They will get a low grade.
무관심: 수업에 관심이 없는 학생들은 공부를 하지 않고 참여하지 않으며 시험에서도 잘하지 못합니다. 낮은 성적을 받게 됩니다. - Generally speaking, I do not give a daily grade for participation. However, I notice your habits. Students who are regularly late, leave early, or are not engaged in the class will get a lower grade.
일반적으로 참여도에 대한 일일 성적은 주지 않습니다. 그러나 당신의 습관을 주의 깊게 지켜봅니다. 정기적으로 늦게 오거나 일찍 떠나거나 수업에 참여하지 않는 학생들은 낮은 성적을 받게 됩니다.
- Active participation is expected in all classes. This means that you are engaged in the class, asking questions, answering questions, and participating in discussions.
- Excused Absences:
- If you have a valid reason for missing a class (e.g., illness, family emergency), please let me know in advance if possible. You will be excused from the class, but you are still responsible for the material covered in the class.
수업을 빠지는 합당한 이유가 있는 경우 (예: 질병, 가족 사정), 가능한 경우 미리 알려주세요. 수업을 빠질 수 있지만 수업에서 다룬 내용에 대한 책임은 여전히 있습니다. - Excused absences will not count against your number of allowed absences. However, they will affect your attendance & participation score because you cannot participate in a class you do not attend.
합당한 이유로 인한 결석은 허용된 결석 횟수에 포함되지 않습니다. 그러나 참석하지 않은 수업에 참여할 수 없기 때문에 출석 및 참여도 점수에 영향을 줍니다. - Generally speaking, students are only allowed to miss 25% of the classes (11 hours in a 45-hour course, 15 hours in a 60-hour course) with excused absences. However, if you have a valid reason for missing more classes, please let me know.
일반적으로, 합당한 이유로 인한 결석을 포함하여 수업의 25% (45시간 강의에서 11시간, 60시간 강의에서 15시간)까지만 허용됩니다. 그러나 더 많은 수업을 빠지는 합당한 이유가 있는 경우, 알려주세요. - If the total number of absences (excused and unexcused) exceeds 35% of the classes (16 hours in a 45-hour course, 21 hours in a 60-hour course), you will fail the course.
총 결석 횟수 (합당한 이유로 인한 결석 및 불합당한 이유로 인한 결석)가 수업의 35% (45시간 강의에서 16시간, 60시간 강의에서 21시간)를 초과하는 경우, 과락이 됩니다.
- If you have a valid reason for missing a class (e.g., illness, family emergency), please let me know in advance if possible. You will be excused from the class, but you are still responsible for the material covered in the class.
Assignments & Practice Exercises 과제 (연습문제) 및 실습 (수업 활동 결과)
- Assignments are generally work you do on your own.
과제는 일반적으로 개인적으로 수행하는 작업입니다. - Practice exercises are work we do together in class.
실습은 수업에서 함께 수행하는 작업입니다. - Most of both types of work will be submitted online (typically via GitHub or Google Forms).
이 두 유형의 대부분 작업은 온라인으로 제출됩니다 (일반적으로 GitHub 또는 Google Forms를 통해). - You are expected to complete all assignments and practice exercises. (This is the best way to ensure you receive a better grade on both the tests and in the class overall.)
모든 과제와 실습을 완료해야 합니다. (이것이 시험과 전반적으로 수업에서 더 나은 성적을 받을 수 있는 가장 좋은 방법입니다.)
Projects (or Research Paper & Presentation) 프로젝트 (또는 논문과 발표)
The following types of projects may be assigned in my courses:
다음 유형의 프로젝트가 강의에서 할당될 수 있습니다:
- Semester-long individual project: This is typically a programming project that you will work on throughout the semester. Usually, the full project code will be included in the selected textbook. You will be expected to complete the project on your own, with all required files, by the end of the semester, as well as a record of your progress on the project throughout the semester with pushes to GitHub.
학기 내내 개인 프로젝트: 일반적으로 학기 내내 작업할 프로그래밍 프로젝트입니다. 일반적으로 전체 프로젝트 코드는 선택한 교재에 포함됩니다. 학기 끝까지 모든 필요한 파일과 함께 프로젝트를 완료하고, 학기 내내 GitHub에 푸시하여 프로젝트 진행 상황을 기록해야 합니다. - Group project: This may be a research project or a programming project that you will work on with a group of students. You will be expected to complete the project with your group members by the end of the semester, as well as a record of your progress on the project throughout the semester with pushes to GitHub.
그룹 프로젝트: 여러 학생들과 함께 작업할 수 있는 연구 프로젝트 또는 프로그래밍 프로젝트일 수 있습니다. 학기 끝까지 그룹 구성원과 함께 프로젝트를 완료하고, 학기 내내 GitHub에 푸시하여 프로젝트 진행 상황을 기록해야 합니다. - Research paper & presentation: This may be a research paper that you will write and present to the class. You will be expected to complete the paper and presentation by the end of the semester.
논문과 발표: 수업에 제출하고 발표할 연구 논문일 수 있습니다. 학기 끝까지 논문과 발표를 완료해야 합니다. - Other: Other types of projects may be assigned as well.
기타: 다른 유형의 프로젝트도 할당될 수 있습니다.
Tests
There will be two tests in this class: a midterm and a final. Both tests may include both written and programming questions. The written questions will be similar to the homework questions, and the programming questions will be similar to the programming assignments. Written questions will be closed-book, and programming questions will be open-book (i.e., you can use any resources you want, including the Internet - however, you must write the code yourself - code copied from ChatGPT often does not function properly and will not receive full credit).
이 강의에서는 두 번의 시험이 있습니다: 중간고사와 기말고사. 두 시험 모두 문제와 프로그래밍 문제를 포함할 수 있습니다. 문제는 과제 문제와 유사하며, 프로그래밍 문제는 프로그래밍 과제와 유사할 것입니다. 문제는 닫힌 책으로, 프로그래밍 문제는 열린 책 (즉, 인터넷을 포함한 모든 자원을 사용할 수 있음 - 그러나 코드는 직접 작성해야 함 - ChatGPT에서 복사한 코드는 종종 제대로 작동하지 않으며 완전한 점수를 받지 못할 수 있음)입니다.
Generally, the midterm will cover the first half of the course, and the final will cover the second half of the course. The final may also include some questions from the first half of the course.
일반적으로 중간고사는 강의의 전반부를 다루고, 기말고사는 후반부를 다룰 것입니다. 기말고사에는 강의의 전반부에서도 일부 문제가 포함될 수 있습니다.
General testing policies: 일반적인 시험 정책:
- You must take the tests at the scheduled time. If you miss a test, you will receive a zero for that test. If you have a valid reason for missing a test (e.g., illness, family emergency), please let me know in advance if possible.
시험은 예정된 시간에 응시해야 합니다. 시험을 빠지는 경우, 해당 시험에 대해 제로 점수를 받게 됩니다. 합당한 이유로 인해 시험을 놓치는 경우 (예: 질병, 가족 사정), 가능한 경우 미리 알려주세요. - You must take the tests on your own. You may not receive help from anyone else during the test. You may not use any resources (like ChatGPT) during the test (except for open-book programming portions).
시험은 스스로 응시해야 합니다. 시험 중에 다른 사람으로부터 도움을 받을 수 없습니다. 시험 중에는 어떤 자원도 사용할 수 없습니다 (ChatGPT와 같은) (프로그래밍 부분을 제외한 열린 책 부분). - You must complete the tests within the time limit. If you do not complete the test within the time limit, you will receive a zero for the test.
시험 시간 내에 시험을 완료해야 합니다. 시험 시간 내에 시험을 완료하지 못하는 경우, 해당 시험에 대해 제로 점수를 받게 됩니다.
Regrading policy: 재평가 정책:
- Use of cellphones during the test is strictly prohibited. If you are caught using a cellphone during the test, you will receive a zero for the test.
시험 중 휴대전화 사용은 엄격히 금지됩니다. 시험 중 휴대전화 사용이 발견되면 해당 시험에 대해 제로 점수를 받게 됩니다. - Bathroom breaks during the test are strictly prohibited. If you leave the room during the test, you will receive a zero for the test.
시험 중 화장실 휴식은 엄격히 금지됩니다. 시험 중에 방을 나가면 해당 시험에 대해 제로 점수를 받게 됩니다. - Talking during the test is strictly prohibited. If you are caught talking during the test, you will receive a zero for the test.
시험 중 이야기하는 것은 엄격히 금지됩니다. 시험 중 이야기하는 것이 발견되면 해당 시험에 대해 제로 점수를 받게 됩니다. - Cheating during the test is strictly prohibited. If you are caught cheating during the test, you will receive a zero for the test.
시험 중 부정행위는 엄격히 금지됩니다. 시험 중 부정행위가 발견되면 해당 시험에 대해 제로 점수를 받게 됩니다. - If you feel that we have made a mistake in grading your test, please submit a regrading request via email and I will consider your request. Please note that regrading of a test may cause your grade to go either up or down.
시험 채점에 오류가 있다고 생각하는 경우, 이메일을 통해 재평가 요청을 제출하면 요청을 고려하겠습니다. 시험 재평가는 성적이 올라가거나 내려갈 수 있음을 유의하십시오.
Collaboration Policy
Homework assignments must be done individually: each student must hand in their own answers. However, it is acceptable to collaborate when figuring out answers and to help each other solve the problems.
과제는 개별적으로 수행되어야 합니다: 각 학생은 자신의 답안을 제출해야 합니다. 그러나 답을 찾는 데 협력하고 문제를 해결하는 데 서로 도와주는 것은 허용됩니다.
We will be assuming that you will be taking the responsibility to make sure you personally understand the solution arising from such collaboration. You also must indicate on each homework with whom you have collaborated.
우리는 이러한 협력에서 발생하는 해결책을 이해하는 책임을 질 것으로 가정할 것입니다. 또한 협력한 사람을 각 과제에 표시해야 합니다.
Late Policy
You will be allowed 6 total homework late days without penalty for the entire semester.
전 학기에 대해 총 6일의 과제 지각일이 허용됩니다. You may be late by up to 6 days on any homework assignment.
어떤 과제에 대해서도 최대 6일까지 지각할 수 있습니다. Once those days are used, you will be penalized according to the following policy:
그 날들을 사용하면 다음 정책에 따라 벌칙을 받게 됩니다:
- Homework is worth full credit at the due time on the due date.
과제는 제출 기한에 제출 시 전액 점수가 부여됩니다. - The allowed late days are counted by day (i.e., each new late day starts at 12:00 am KST).
허용된 지각일은 일별로 계산됩니다 (즉, 새로운 지각일은 한국 표준시 오전 12시에 시작됩니다). - Once the allowed late days are exceeded, the penalty is 50% per late day counted by hour (i.e., 2.0833% per hour).
허용된 지각일을 초과하면, 지각일당 50%의 벌칙이 시간별로 계산됩니다 (즉, 시간당 2.0833%). - The homework is worth zero credit 48 hours after exceeding the late day limit.
지각일 한도를 초과한 48시간 후에는 과제가 0점이 됩니다.
You must turn in 75% of the practices and assignments, even if for zero credit, in order to pass the course.
과제를 제출해야 하는 날짜에 과제를 제출하지 않으면 0점이 됩니다.
과제는 48시간 후에는 0점이 됩니다.
Generally speaking, I do not accept late submissions for practice exercises. However, if you have a valid reason for submitting a practice exercise late, please let me know in advance if possible.
일반적으로 실습에 대한 늦은 제출은 받지 않습니다. 그러나 실습을 늦게 제출하는 합당한 이유가 있는 경우, 가능한 경우 미리 알려주세요.
Regrade Policy
If you feel that we have made a mistake in grading your homework, please submit a regrading request via email and I will consider your request.
과제 채점에 오류가 있다고 생각하는 경우, 이메일을 통해 재평가 요청을 제출하면 요청을 고려하겠습니다.
Please note that regrading of a homework may cause your grade to go either up or down.
과제 재평가는 성적이 올라가거나 내려갈 수 있음을 유의하십시오.
Resources 자료실
Computer Software / 소프트웨어
The software we will be using is listed below. 수업에서 사용할 소프트웨어가 다음과 같다.
Textbook Resources / 교재자료
Do it! 실습 파일과 PDF 전자책
Tutorials / 튜토리얼
Instructor 강사소개
- Instructor Aaron Snowberger
- Email: aaronkr.trainer@gmail.com
- KakaoTalk: AaronKr
Aaron Snowberger earned his Ph.D. in Information and Communications Engineering from Hanbat National University in South Korea in 2023. He also holds degrees in Computer Science and Media Design. He has taught technology courses for over 8 years, English for over 15 years, and has freelanced as a web developer and magazine designer for over 5 years. His current research interests include computer vision, natural language processing, image processing, signal processing, and machine learning.
Aaron Snowberger는 2023년 한국 한밭대학교에서 정보통신공학 박사 학위를 취득했습니다. 그는 또한 컴퓨터 과학 및 미디어 디자인 학위를 취득했습니다. 그는 8년 이상 기술 과정을 가르쳤고, 15년 이상 영어를 가르쳤으며, 5년 이상 웹 개발자 및 잡지 디자이너로 프리랜서로 일했습니다. 그의 현재 연구 관심사는 컴퓨터 비전, 자연어 처리, 이미지 처리, 신호 처리 및 머신 러닝입니다.