PhD Seminar • Algorithms and Complexity • Complexity Estimation of DNA Computing Algorithms for the Subset Sum ProblemExport this event to calendar

Friday, March 25, 2022 — 9:00 AM EDT

Please note: This PhD seminar will be given online.

Zihao Wang, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Lila Kari

Some DNA computing approaches have been proposed to solve NP-complete problems in polynomial time with some trade-offs, such as having an exponential number of computing agents, and some were realized in a proof-of-concept experiment. The network biocomputing method is another example of a non-conventional approach to NP-complete problems. Regardless of the fundamental differences between these methods, we can compare their time, space and energy complexities. For the comparison, the subset sum problem is chosen as the benchmark problem, and different problem sizes and types of input sets are considered. In brief, the advantages of the DNA computing approach to the subset sum problem include the polynomial growth of the computing time. In contrast, the benefits of the network biocomputing approach include the smaller amount of required computing agents.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/99139019529?pwd=SThsZmtER1c0eWJSbXlkSXZ5aWhEZz09.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2023 (2)
    1. January (2)
  2. 2022 (236)
    1. December (11)
    2. November (28)
    3. October (15)
    4. September (12)
    5. August (29)
    6. July (23)
    7. June (17)
    8. May (20)
    9. April (24)
    10. March (22)
    11. February (16)
    12. January (19)
  3. 2021 (210)
    1. December (21)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  4. 2020 (217)
  5. 2019 (255)
  6. 2018 (217)
  7. 2017 (36)
  8. 2016 (21)
  9. 2015 (36)
  10. 2014 (33)
  11. 2013 (23)
  12. 2012 (4)
  13. 2011 (1)
  14. 2010 (1)
  15. 2009 (1)
  16. 2008 (1)